基本技能

链表相关的核心点

  • null/nil 异常处理
  • dummy node 哑巴节点
  • 快慢指针
  • 插入一个节点到排序链表
  • 从一个链表中移除一个节点
  • 翻转链表
  • 合并两个链表
  • 找到链表的中间节点

常见题型

remove-duplicates-from-sorted-list

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

  1. var deleteDuplicates = function(head) {
  2.     let cur = head;
  3.     while(cur) {
  4.         while(cur.next && cur.val == cur.next.val) {
  5.             cur.next = cur.next.next;
  6.         };
  7.         cur = cur.next;
  8.     };
  9.     return head
  10. };

remove-duplicates-from-sorted-list-ii

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。

思路：链表头结点可能被删除，所以用 dummy node 辅助删除

  1. var deleteDuplicates = function(head) {
  2.     var dummyHead = new ListNode(null, head);
  3.     head = dummyHead;
  4.     while(head.next && head.next.next) {
  5.        if(head.next.val == head.next.next.val) {
  6.            let x = head.next.val;
  7.            while(head.next && head.next.val == x) {
  8.                head.next = head.next.next;
  9.            }
  10.        } else {
  11.            head = head.next;
  12.        }
  13.     }
  15.     return dummyHead.next;
  16. };

注意点
• A->B->C 删除 B，A.next = C
• 删除用一个 Dummy Node 节点辅助（允许头节点可变）
• 访问 X.next 、X.value 一定要保证 X !== null

reverse-linked-list

反转一个单链表。

思路：用一个 prev 节点保存向前指针，temp 保存向后的临时指针

  1. // 递归
  2. var reverseList = function(head) {
  3.     if(head == null || head.next == null) return head;
  5.     let last = reverseList(head.next);
  6.     head.next.next = head;
  7.     head.next = null;
  8.     return last;
  9. };
  12. // 遍历版本
  13. var reverseList = function(head) {
  14.     let prev = null;
  15.     let curr = head;
  16.     while (curr) {
  17.         const next = curr.next;
  18.         curr.next = prev;
  19.         prev = curr;
  20.         curr = next;
  21.     }
  22.     return prev;
  23. };

reverse-linked-list-ii

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路：先遍历到 m 处，翻转，再拼接后续，注意指针处理

  1. var reverseBetween = function(head, left, right) {
  3.     var dummyHead = new ListNode(null, head);
  4.     var pre = dummyHead;
  5.     for( var i = 0; i < left - 1; ++i) {
  6.         pre = pre.next;
  7.     }
  9.     var cur = pre.next;
  10.     for ( var i = 0; i < right - left; ++i) {
  11.         var next = cur.next;
  12.         cur.next = next.next;
  13.         next.next = pre.next;
  14.         pre.next = next;
  15.     }
  16.     return dummyHead.next
  17. };

merge-two-sorted-lists

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：通过 dummy node 链表，连接各个元素

  1. var mergeTwoLists = function(l1, l2) {
  2.     if (l1 === null) {
  3.         return l2;
  4.     } else if (l2 === null) {
  5.         return l1;
  6.     } else if (l1.val < l2.val) {
  7.         l1.next = mergeTwoLists(l1.next, l2);
  8.         return l1;
  9.     } else {
  10.         l2.next = mergeTwoLists(l1, l2.next);
  11.         return l2;
  12.     }
  13. };

partition-list

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

思路：将大于 x 的节点，放到另外一个链表，最后连接这两个链表

  1. var small = new ListNode(0);
  2.     var large = new ListNode(0);
  3.     var smallHead = small;
  4.     var largeHead = large;
  6.     while(head) {
  7.         if(head.val >= x) {
  8.             large.next = head
  9.             large = large.next;
  10.         } else {
  11.             small.next = head;
  12.             small = small.next;
  13.         }
  14.         head = head.next
  15.     }
  16.     large.next = null;
  17.     small.next = largeHead.next;
  18.     return smallHead.next;

哑巴节点使用场景

当头节点不确定的时候，使用哑巴节点

sort-list

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

思路：归并排序，找中点和合并操作

注意点

  • 快慢指针 判断 fast 及 fast.Next 是否为 nil 值
  • 递归 mergeSort 需要断开中间节点
  • 递归返回条件为 head 为 nil 或者 head.Next 为 nil

reorder-list

给定一个单链表 L：L→L→…→L__n→L 将其重新排列后变为： L→L__n→L→L__n→L→L__n→…

思路：找到中点断开，翻转后面部分，然后合并前后两个链表

linked-list-cycle

给定一个链表，判断链表中是否有环。

思路：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 1
链表 - 图1

  1. var hasCycle = function(head) {
  2.     if(head == null) return false;
  4.     var fast = head.next, slow = head;
  6.     while(fast !== slow) {
  7.         if(fast === null || fast.next === null) {
  8.             return false;
  9.         }
  10.         fast = fast.next.next;
  11.         slow = slow.next
  12.     }
  13.     return true
  14. };

linked-list-cycle-ii

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

思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点
链表 - 图2

  1. var detectCycle = function(head) {
  2.      // 思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点
  3.     if(head == null) return head;
  5.     var fast = head.next, slow = head;
  7.     while(fast && fast.next) {
  8.         if(fast === slow) {
  9.             // 慢指针重新从头开始移动，快指针从第一次相交点下一个节点开始移动
  10.             slow = head;
  11.             fast = fast.next;
  12.             while(fast !== slow) {
  13.                 fast = fast.next;
  14.                 slow e= slow.next;
  15.             }
  16.             return slow
  17.         }
  19.         fast = fast.next.next;
  20.         slow = slow.next;
  21.     }
  23.     return null
  24. };

坑点

  • 指针比较时直接比较对象，不要用值比较，链表中有可能存在重复值情况
  • 第一次相交后，快指针需要从下一个节点开始和头指针一起匀速移动

另外一种方式是 fast=head,slow=head

这两种方式不同点在于，一般用 fast=head.Next 较多，因为这样可以知道中点的上一个节点，可以用来删除等操作。

  • fast 如果初始化为 head.Next 则中点在 slow.Next
  • fast 初始化为 head,则中点在 slow

palindrome-linked-list

请判断一个链表是否为回文链表。

copy-list-with-random-pointer

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。

思路：1、hash 表存储指针，2、复制节点跟在原节点后面

总结

链表必须要掌握的一些点，通过下面练习题，基本大部分的链表类的题目都是手到擒来~

  • null/nil 异常处理
  • dummy node 哑巴节点
  • 快慢指针
  • 插入一个节点到排序链表
  • 从一个链表中移除一个节点
  • 翻转链表
  • 合并两个链表
  • 找到链表的中间节点

练习