Day1: 单链表的六大解题思路

21. 合并两个有序链表

我是链接

生成一个哑节点current，比较list1和 list2 指针，将较小的值的指针拼接在current后，current指针前进，最后将剩余的指针全拼在current后。

利用哑节点可以避免处理空指针的情况，减少不必要的麻烦。

  1. var mergeTwoLists = function(list1, list2) {
  2.   // 生成哑节点
  3.   let dummyNode = new ListNode(-1)
  4.   let current = dummyNode
  5.   while (list1 && list2) {
  6.       // 将较小的值的指针拼接在current后
  7.     if (list1.val < list2.val) {
  8.       current.next = list1
  9.       list1 = list1.next
  10.     } else {
  11.       current.next = list2
  12.       list2 = list2.next
  13.     }
  14.     // 指针继续前进
  15.     current = current.next
  16.   }
  17.   // 将剩余的指针全拼在current后
  18.   current.next = list1 || list2
  19.   return dummyNode.next
  20. };

23.合并k个链表

我是链接

最小堆

由于js没有堆的数据结构，所以将链表所有节点存入一个数组中，再将数组排序，再从数组重新生成一个完整链表

优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 pq，

所以算法整体的时间复杂度是 **O(Nlogk)**，其中 **k** 是链表的条数，**N** 是这些链表的节点总数。

  1. var mergeKLists = function(lists) {
  2.   let arr = []
  3.   // 将所有【链表节点】存入数组，不能对lists使用flat的数组方法
  4.   lists.map(i => {
  5.     let node = i
  6.     while (node) {
  7.       arr.push(node.val)
  8.       node = node.next
  9.     }
  10.   })
  11.   // 排序
  12.   arr.sort((a, b) => a - b)
  13.   let dummyNode = new ListNode(-1)
  14.   let current = dummyNode
  15.   // 重新生成链表
  16.   arr.map(num => {
  17.     current.next = new ListNode(num)
  18.     current = current.next
  19.   })
  20.   return dummyNode.next
  21. };

归并合并排序链表

输入k个排序链表，将其拆分成前k/2个链表和后k/2个链表，这前k/2个链表和后k/2个链表分别合并成两个排序的链表，再将两个排序的链表合并，所有链表就都合并了。

  • 下面代码中递归调用栈的深度为O(logn)，所以空间复杂度为O(logn)
  • 因为使用的是归并排序的思路，所以它的时间复杂度为O(nlogn)
  1. var mergeKLists = function(lists) {
  2.   if (!lists.length) {
  3.     return null
  4.   }
  5.   /* 合并两个链表为升序链表 */
  6.   var mergeTwoLists = function(list1, list2) {
  7.     // 生成哑节点
  8.     let dummyNode = new ListNode(-1)
  9.     let current = dummyNode
  10.     while (list1 && list2) {
  11.       // 将较小的值的指针拼接在current后
  12.       if (list1.val < list2.val) {
  13.         current.next = list1
  14.         list1 = list1.next
  15.       } else {
  16.         current.next = list2
  17.         list2 = list2.next
  18.       }
  19.       // 指针继续前进
  20.       current = current.next
  21.     }
  22.     // 将剩余的指针全拼在current后
  23.     current.next = list1 || list2
  24.     return dummyNode.next
  25.   };
  26.   const mergeLists = (lists, start = 0, end = lists.length) => {
  27.     // 仅有一个节点时直接返回 lists， 无需拆分
  28.     if (start + 1 === end) {
  29.       return lists[start]
  30.     }
  31.     // 拆分成两个链表，分别进行排序
  32.     const mid = Math.floor((start + end)/2) // 也可写作 const mid = (start + end) >> 1
  33.     const l1 = mergeLists(lists, start, mid)
  34.     const l2 = mergeLists(lists, mid, end)
  35.     return mergeTwoLists(l1, l2)
  36.   }
  37.   // 前闭后开区间
  38.   return mergeLists(lists, 0, lists.length)
  39. };

19.删除链表的倒数第 N 个结点

我是链接

生成哑结点，让快指针先走N步，快指针到达时，慢指针到达倒数N + 1结点处，再删除

  1. var removeNthFromEnd = function(head, n) {
  2.   let dummyNode = new ListNode(-1)
  3.   dummyNode.next = head
  4.   let fast = dummyNode
  5.   let slow = dummyNode
  6.   // 快指针先走 N 步
  7.   while (n --) {
  8.     fast = fast.next
  9.   }
  10.   // 快指针到达终点，慢指针到达倒数N + 1处
  11.   while (fast && fast.next) {
  12.     fast = fast.next
  13.     slow = slow.next
  14.   }
  15.   // 删除
  16.   slow.next = slow.next.next
  17.   return dummyNode.next
  18. };

876. 链表的中间结点

我是链接

设置快慢指针，让快指针速度是慢指针的2倍，快指针到达时，慢指针刚好在链表中点。

  1. var middleNode = function(head) {
  2.   let slow = fast = head
  3.   while (fast && fast.next) {
  4.     fast = fast.next.next
  5.     slow = slow.next
  6.   }
  7.   return slow
  8. };

环形链表II - 环位置

我是链接

设置快(2)慢(1)指针，若快慢指针相遇，则为环形

可以看到，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置

  1. var detectCycle = function(head) {
  2.   let slow = head
  3.   let fast = head
  4.   let isLoop = false
  5.   while (fast && fast.next) {
  6.     fast = fast.next.next
  7.     slow = slow.next
  8.     if (slow === fast) {
  9.       // 快慢指针相遇，则为环形
  10.       isLoop = true
  11.       // 跳出循环
  12.       break
  13.     }
  14.   }
  15.   // 确认是环形，找出pos
  16.   if (isLoop) {
  17.     slow = head
  18.     while (slow !== fast) {
  19.       slow = slow.next
  20.       fast = fast.next
  21.     }
  22.   }
  23.   return isLoop ? slow : null
  24. };

160. 相交链表

我是链接

我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，

让 p2 遍历完链表 B 之后开始遍历链表 A，

这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点

  2. var getIntersectionNode = function(headA, headB) {
  3.   let p1 = headA
  4.   let p2 = headB
  5.   while (p1 != p2) {
  6.     // 遍历完后遍历另一支链表
  7.     p1 = p1 ? p1.next : headB
  8.     p2 = p2 ? p2.next : headA
  9.   }
  10.   return p1
  11. };

Day2: 递归反转链表

206. 反转整个链表

我是链接

递归

将递归函数定义为：输入一个结点head，将以【head为起点】的链表反转，返回反转后的头节点.

递归函数需要base case，当链表仅有一个节点时，反转后也是自己，直接返回即可

  1. var reverseList = function(head) {
  2.   // 链表仅有一个节点，直接返回
  3.   if (head === null || head.next === null) {
  4.     return head
  5.   }
  6.   // 将head.next为起点的链表反转，返回反转后的头结点
  7.   const last = reverseList(head.next)
  8.   head.next.next = head
  9.   head.next = null
  10.   return last
  11. };

迭代

链表 - 图1

  1. var reverseList = function(head) {
  2.   let pre = null
  3.   let current = head
  4.   while (current) {
  5.     // 临时变量存储未反转的链表起点
  6.     const temp = current.next
  7.     current.next = pre
  8.     pre = current
  9.     current = temp
  10.   }
  11.   return pre
  12. };

反转链表的前n个节点

递归函数定义： 反转以head为起点的前n个节点链表，返回反转后的头节点

basecase:

  1. /**
  2. * A -> B -> C -> D
  3. * A <- B C -> D
  4. * A -> C
  5. */
  6. let rest = null
  7. var reverseN = function(head, n) {
  8.   if (n === 1) {
  9.     // 返回当前节点
  10.     // 并记录 n + 1 的节点位置（未反转部分的链表起点）
  11.     rest = head.next
  12.     return head
  13.   }
  14.   // 反转 head.next 为起点的 n - 1 个节点
  15.     const last = reverseN(head.next, n - 1)
  16.   head.next.next = head
  17.   // 反转后的节点和未反转的节点连接起来
  18.   head.next = rest
  19.   return last
  20. };

92.反转链表的一部分节点

我是链接

basecase：当 left 为 1 时，相当于反转前N个节点。

反转head起始的[left，right]区间就相当于反转 head.next 起始的[left - 1, right - 1]区间

  1. var reverseBetween = function(head, left, right) {
  2.   if (left === 1) {
  3.     return revereN(head, right)
  4.   }
  5.   // 以 head.next 为下标 1，那就是 反转head.next为起点的 left - 1, right - 1 区间
  6.   head.next = reverseBetween(head.next, left - 1, right - 1)
  7.   return head
  8. };
  10. // 反转前 N 个链表，相当于 left = 1 开始
  11. let rest = null
  12. const revereN = (head, n) => {
  13.   if (n === 1) {
  14.     rest = head.next
  15.     return head
  16.   }
  17.   const last = revereN(head.next, n - 1)
  18.   head.next.next = head
  19.   head.next = rest
  20.   return last
  21. }

25. K个一组反转链表

我是链接

记录下每k个一组的起始节点和结束节点，不足 k 个的直接返回head。

将反转起始节点和结束节点的链表并拼接到剩余未反转的链表上

  1. var reverseKGroup = function(head, k) {
  2.   // 用start 和 end 记录每k个需要反转的起始节点、结束起点
  3.   let start = end = head
  4.   // 不足 k 个即end 到达了 null，直接返回 head
  5.   for (let i = 0; i < k; i ++) {
  6.     if (end === null) {
  7.       return head
  8.     }
  9.     // 得到第 k 个节点 end
  10.     end = end.next
  11.   }
  12.   // 反转 start 到 end 间的链表
  13.   const last = reverse(start, end)
  14.   start.next = reverseKGroup(end, k)
  15.   return last
  16. };
  18. // 前面的反转整个链表：其实就是反转 head 到 null 间的链表
  19. // 迭代
  20. const reverse = (start, end = null) => {
  21.   let pre = null
  22.   let current = start
  23.   while (current !== end) {
  24.     const temp = current.next
  25.     current.next = pre
  26.     pre = current
  27.     current = temp
  28.   }
  29.   return pre
  30. }

234.回文链表

我是链接

找出中点，将中点后的节点反转，记录为右指针，比较左指针（起始）和右指针的节点值，不同则返回false

  2. //  反转链表
  3.  const reverse = (head) => {
  4.    if (head === null || head.next == null) {
  5.      return head
  6.    }
  7.    const last = reverse(head.next)
  8.    head.next.next = head
  9.    head.next = null
  10.    return last
  11.  }
  12. var isPalindrome = function(head) {
  13.   // 找出中点
  14.   let fast = slow = head
  15.   while (fast && fast.next) {
  16.     fast = fast.next.next
  17.     slow = slow.next
  18.   }
  19.   // 注意奇数链表，中点多走一步
  20.   if (fast !== null) {
  21.     slow = slow.next
  22.   }
  23.   let left = head
  24.   let right = reverse(slow)
  25.   while (right) {
  26.     if (left.val != right.val) {
  27.       return false
  28.     }
  29.     left = left.next
  30.     right = right.next
  31.   }
  32.   return true
  33. };