链表

单链表反转

function Node(value, next) {
  this.value = value
  this.next = next
}

const n1 = new Node(1)
n1.next = new Node(2)
n1.next.next = new Node(3)

function reverse(head) {
  let pre = null
  let next = null
  while (head) {
    next = head.next
    head.next = pre
    pre = head
    head = next
  }
  return pre
}

let n2 = reverse(n1)
while (n2) {
  console.log(n2.value) //3 2 1
  n2 = n2.next
}

双向链表反转

function DoubleNode(value,last,next){
  this.value = value
  this.last = last
  this.next = next
}

let n1 = new DoubleNode(1,null)
n1.next = new DoubleNode(2,n1)
n1.next.next = new DoubleNode(3,n1.next)

function reverseDouble(head){
  let pre = null
  let next = null
  while (head){
    next = head.next
    head.next = pre
    head.last = next
    pre = head
    head = next
  }
  return pre
}

K 个一组翻转链表

leetcode上的题目： K 个一组翻转链表

var reverseKGroup = function(head, k) {
  let start = head
  let end = getGroupEnd(start,k)
  if(!end){
    return start
  }
  head = end
  reverse(start,end)
  let lastEnd = start
  while(start.next){
    start = start.next
    end = getGroupEnd(start,k)
    if(!end){
      return head
    }
    reverse(start,end)
    lastEnd.next = end
    lastEnd = start
  }
  return head
};

function getGroupEnd(start,k){
  while(--k > 0 && start){
    start = start.next
  }
  return start
}

function reverse(start,end){
  let cur = start
  let pre = null
  let next = null
  while(start !== end){
    next = start.next
    start.next = pre
    pre = start
    start = next
  }
  next = start.next
  start.next = pre
  cur.next = next
}

有序链表合并

leetcode上的题目：合并两个有序链表

var mergeTwoLists = function (list1, list2) {
  if (!list1 || !list2) {
    return list1 ? list1 : list2
  }
  let head = list1.val < list2.val ? list1 : list2
  let cur1 = head.next
  let cur2 = head === list1 ? list2 : list1
  let pre = head
  while (cur1 && cur2) {
    if (cur1.val < cur2.val) {
      pre.next = cur1
      cur1 = cur1.next
    } else {
      pre.next = cur2
      cur2 = cur2.next
    }
    pre = pre.next
  }
  pre.next = cur1 ? cur1 : cur2
  return head
};

快慢指针

快慢指针：快指针每次沿链表向前移动2，慢指针每次向前移动1次。

应用：判断单链表是否为回文链表：（leetcode上的题目：回文链表）

思路：遍历链表，将值拷贝到一个栈中；再次遍历链表，对比每次出栈的值是否相同即可。

优化：使用快慢指针，在遍历到一半时开始进行比较即可，节省一半的额外空间。

var isPalindrome = function(head) {
  if(!head || !head.next) return true
  let fast = head
  let slow = head
  const stack = []
  while(fast && fast.next){
    stack.push(slow.val)
    fast = fast.next.next
    slow = slow.next
  }
  if(fast) slow = slow.next
  while(slow){
    if(stack.pop() !== slow.val) return false
    slow = slow.next
  }
  return true
};

继续优化：只使用O(1)的额外空间复杂度，慢指针在走的过程中将前半部分的链表反转

var isPalindrome = function(head) {
  if(!head || !head.next) return true
  let fast = head,slow = head,cur = head
  let pre = null
  while(fast && fast.next){
    fast = fast.next.next
    slow = slow.next
    cur.next = pre
    pre = cur
    cur = slow
  }
  if(fast) slow = slow.next
  while(slow){
    if(slow.val !== pre.val) return false
    slow = slow.next
    pre = pre.next
  }
  return true
};

注：上面未将链表的反转部分还原

环形链表

leetcode上的题目：环形链表 II

返回链表开始入环的第一个节点，如果链表无环，则返回 null。

var detectCycle = function(head) {
  if(!head || !head.next || !head.next.next) return null
  let fast = head.next.next, slow = head.next
  while(fast !== slow){
    fast = fast.next?.next
    slow = slow.next
    if(!fast) return null
  }
  fast = head
  while(fast !== slow){
    fast = fast.next
    slow = slow.next
  }
  return slow
};

假设环外有a个节点，环内有b个节点，则第a+nb个节点一定是入口节点。使用快慢指针判断有环无环，快慢指针相遇时在第nb个节点，再走a步即可。