List article

Construct a linked list given an array

function createHead(array) {
    let head = {
      val: array[0].next: null
    }
    let p = head
    for(let i = 1; i < array.length; i++) {
      let obj = {
        val: array[i],
        next: null
      }
      p.next = obj
      p = p.next
    }
    return head
  }
Copy the code

Reverse a linked list

/ / method
function reverse(head) {
  if(head === null || head.next === null) {
    return head
  }
  let newHead = reverse(head.next)
  head.next.next = head
  head.next = null

  return newHead
}

/ / method 2
function reverse2(head) {
  let pre = null
  let next = null

  while(head) {
    next = head.next
    head.next = pre
    pre = head
    head = next
  }
  return pre
}
Copy the code

List merge (ordered list)

/ / method
function Merge(l1, l2) {
  if(l1 === null || l2 === null) {
    return l1 || l2
  }
  if(l1.val < l2.val) {
    l1.next = Merge(l1.next, l2)
    return l1
  } else {
    l2.next = Merge(l1, l2.next)
    return l2
  }
}

/ / method 2
function Merge2(l1,l2) {
  let head = {
    val: 0.next: null
  }
  let p = head

  while(l1 && l2) {
    if(l1.val < l2.val) {
      p.next = l1
      l1 = l1.next
    } else {
      p.next = l2
      l2 = l2.next
    }
    p = p.next
  }
  p.next = l1 || l2

  return head.next
}
Copy the code

List merge (unordered list)

function Merge(l1, l2) {
  let head = {
    val: 0.next: null
  }
  let p = head
  while(l1) {
    p.next = l1
    l1 = l1.next
    p = p.next
  }
  p.next = l2
  return head.next
}
Copy the code

Find the middle of the list

function middle(head) {
  let fast = head
  let slow = head

  while(fast.next && fast.next.next) {
    fast = fast.next.next
    slow = slow.next
  }
  return slow
}
Copy the code

Check whether the linked list has a ring, if there is a ring return encounter node

function isLoop(head) {
  if(head.next === null) {
    return false
  }

  let fastNode = head
  let slowNode = head
  while(fastNode.next && fastNode.next.next && slowNode ! == fastNode) { slowNode = slowNode.next fastNode = fastNode.next.next }if(slowNode === fastNode) {
    return true
  }
  return false
}
Copy the code

Returns the KTH node from last of the list

function findK(head, k) {
  let p = head
  let q = p
  for(let i = 0; i < k; i++) {
    if (q === null) {
      return -1
    }
    q = q.next
  }

  while(q) {
    q = q.next
    p = p.next
  }
  return p
}
Copy the code

Deletes the node specified in the linked list

function deleteNode(head, k) {
  let p = head
  let j = 1

  while(p.next && j < k - 1) {
    p = p.next
    j++
  }
  let tmp = p.next
  p.next = tmp.next
  return head
}
Copy the code

List order

function sort(head) {
  let cur = null, tail = null
  cur = head
  while(cur.next ! == tail) {while(cur.next ! == tail) {if(cur.val > cur.next.val) {
        let tmp = cur.val
        cur.val = cur.next.val
        cur.next.val = tmp
      }
      cur = cur.next
    }
    tail = cur
    cur = head
  }
  return head
}
Copy the code