数组是一种顺序表,index 与 value 之间是一种顺序映射,以 \(O(1)\) 的复杂度访问数据元素。但是,若要在表的中间部分插入(或删除)某一个元素时,需要将后续的数据元素进行移动,复杂度大概为 \(O(n)\)。链表(Linked List)是一种链式表,克服了上述的缺点,插入和删除操作均不会引起元素的移动;数据结构定义如下:
- public class ListNode {
- String val;
- ListNode next;
- // ...
- }
常见的链表有单向链表(也称之为 chain),只有 next 指针指向后继结点,而没有 previous 指针指向前驱结点。
链表的插入与删除操作只涉及到 next 指针的更新,而不会移动数据元素。比如,要在 FAT 与 HAT 插入结点 GAT,如图所示:
Java 实现:
- ListNode fat,
- gat;
- gat.next = fat.next;
- fat.next = gat;
又比如,要删除结点 GAT,如图所示:
Java 实现:
- fat.next = fat.next.next;
从上述代码中,可以看出:因为没有前驱指针,一般在做插入和删除操作时,我们需要通过操作前驱结点的 next 指针开始。
LeetCode 题目 | 归类 |
---|---|
237. Delete Node in a Linked List | 删除 |
203. Remove Linked List Elements | |
19. Remove Nth Node From End of List | |
83. Remove Duplicates from Sorted List | |
82. Remove Duplicates from Sorted List II | |
24. Swap Nodes in Pairs | 移动 |
206. Reverse Linked List | |
92. Reverse Linked List II | |
61. Rotate List | |
86. Partition List | |
328. Odd Even Linked List | |
21. Merge Two Sorted Lists | 合并 |
23. Merge k Sorted Lists | |
141. Linked List Cycle | 有环 |
142. Linked List Cycle II | 有环 |
234. Palindrome Linked List | |
143. Reorder List | |
160. Intersection of Two Linked Lists | |
2. Add Two Numbers | |
445. Add Two Numbers II |
237. Delete Node in a Linked List
删除指定结点。由于是单向链表,因此只需更新待删除节点即可。
- public void deleteNode(ListNode node) {
- node.val = node.next.val;
- node.next = node.next.next;
- }
203. Remove Linked List Elements
删除指定值的结点。用两个指针实现,curr 用于遍历,prev 用于暂存前驱结点。
- public ListNode removeElements(ListNode head, int val) {
- ListNode fakeHead = new ListNode(Integer.MIN_VALUE);
- fakeHead.next = head;
- for (ListNode curr = head, prev = fakeHead; curr != null; curr = curr.next) {
- if (curr.val == val) { // remove
- prev.next = curr.next;
- } else { // traverse
- prev = prev.next;
- }
- }
- return fakeHead.next;
- }
19. Remove Nth Node From End of List
删除链表的倒数第 n 个结点。思路:因为单向链表是没有前驱指针的,所以应找到倒数第 n+1 个结点;n 有可能等于链表的长度,故先 new 一个 head 的前驱结点 fakeHead。用两个指针 slow、fast 从 fakeHead 开始,先移动 fast n+1 步,使得其距离 slow 为 n+1;然后,两个指针同步移动,当 fast 走到 null 时,slow 即处于倒数第 n+1 个结点,删除 slow 的 next 结点即可。
- public ListNode removeNthFromEnd(ListNode head, int n) {
- ListNode fakeHead = new ListNode(Integer.MIN_VALUE);
- fakeHead.next = head;
- ListNode slow = fakeHead,
- fast = fakeHead;
- for (int i = 1; i <= n + 1; i++) {
- fast = fast.next;
- }
- while (fast != null) {
- fast = fast.next;
- slow = slow.next;
- }
- slow.next = slow.next.next; // the n-th node from end is `slow.next`
- return fakeHead.next;
- }
83. Remove Duplicates from Sorted List
删除有序链表中的重复元素。处理思路有上一问题类似,不同的是判断删除的条件。
- public ListNode deleteDuplicates(ListNode head) {
- ListNode fakeHead = new ListNode(Integer.MIN_VALUE);
- fakeHead.next = head;
- for (ListNode curr = head, prev = fakeHead; curr != null && curr.next != null; curr = curr.next) {
- if (curr.val == curr.next.val) { // remove
- prev.next = curr.next;
- } else {
- prev = prev.next;
- }
- }
- return fakeHead.next;
- }
82. Remove Duplicates from Sorted List II
上一问题的升级版,删除所有重复元素结点。在里层增加一个 while 循环,跳过重复元素结点。
public ListNode deleteDuplicates(ListNode head) { ListNode fakeHead = new ListNode(Integer.MIN_VALUE); fakeHead.next = head; for (ListNode curr = head, prev = fakeHead; curr != null; curr = curr.next) { while (curr.next != null && curr.val == curr.next.val) { // find the last duplicate curr = curr.next; } if (prev.next == curr) prev = prev.next; else prev.next = curr.next; } return fakeHead.next; }
24. Swap Nodes in Pairs
链表中两两交换。按 step = 2 遍历链表并交换;值得注意的是在更新 next 指针是有次序的。
public ListNode swapPairs(ListNode head) { ListNode fakeHead = new ListNode(Integer.MIN_VALUE); fakeHead.next = head; for (ListNode prev = fakeHead, p = head; p != null && p.next != null; ) { ListNode temp = p.next.next; prev.next = p.next; // update next pointer p.next.next = p; p.next = temp; prev = p; p = temp; } return fakeHead.next; }
206. Reverse Linked List
逆序整个链表。逆序操作可以看作:依次遍历链表,将当前结点插入到链表头。
public ListNode reverseList(ListNode head) { ListNode newHead = null; for (ListNode curr = head; curr != null; ) { ListNode temp = curr.next; curr.next = newHead; // insert to the head of list newHead = curr; curr = temp; } return newHead; }
92. Reverse Linked List II
上一问题的升级,指定区间 [m, n] 内做逆序;相当于把该区间的链表逆序后,再拼接到原链表中。
public ListNode reverseBetween(ListNode head, int m, int n) { ListNode newHead = null, curr = head, firstHead = null, firstHeadPrev = null; for (int i = 1; curr != null && i <= n; i++) { if (i < m - 1) { curr = curr.next; continue; } if (i == m - 1) { firstHeadPrev = curr; // mark first head previous node curr = curr.next; } else { if (i == m) firstHead = curr; // mark first head node ListNode temp = curr.next; curr.next = newHead; newHead = curr; curr = temp; } } firstHead.next = curr; if (firstHeadPrev != null) firstHeadPrev.next = newHead; if (m == 1) return newHead; return head; }
61. Rotate List
指定分隔位置,将链表的左右部分互换。只需修改左右部分的最后节点的 next 指针即可,有一些 special case 需要注意,诸如:链表为空,k 为链表长度的倍数等。为了得到链表的长度,需要做一次 pass。故总共需要遍历链表两次。
public ListNode rotateRight(ListNode head, int k) { if (head == null || k == 0) return head; int n = 0, i; ListNode curr, leftLast = head, rightFist, rightLast = head; for (curr = head; curr != null; curr = curr.next) { // get the length of list n++; } k %= n; // k maybe larger than n if (k == 0) return head; for (i = 1, curr = head; i <= n; i++, curr = curr.next) { // mark the split node if (i == n - k) leftLast = curr; if (i == n) rightLast = curr; } rightFist = leftLast.next; leftLast.next = null; rightLast.next = head; return rightFist; }
86. Partition List
类似于的 partition,不同的是要保持链表的原顺序。思路:用两个链表,一个保留小于指定数 x,一个保留不大于指定数 x;最后拼接到一起即可。
public ListNode partition(ListNode head, int x) { if (head == null) return null; ListNode lt = new ListNode( - 1), gte = new ListNode( - 2); // less than, greater than and equal ListNode p, p1, p2; for (p = head, p1 = lt, p2 = gte; p != null; p = p.next) { if (p.val < x) { p1.next = p; p1 = p1.next; } else { p2.next = p; p2 = p2.next; } } p2.next = null; p1.next = gte.next; return lt.next; }
328. Odd Even Linked List
链表分成两部分:偶数编号与奇数编号,将偶数链表拼接到奇数链表的后面。
public ListNode oddEvenList(ListNode head) { if (head == null || head.next == null) return head; ListNode odd = head, even = head.next, evenHead = head.next; while (odd.next != null && odd.next.next != null) { odd.next = odd.next.next; odd = odd.next; if (even != null && even.next != null) { even.next = even.next.next; even = even.next; } } odd.next = evenHead; // splice even next to odd return head; }
21. Merge Two Sorted Lists
合并两个有序链表。比较简单,分情况比较。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode( - 1), p, p1, p2; for (p = head, p1 = l1, p2 = l2; p1 != null || p2 != null; p = p.next) { if (p1 != null) { if (p2 != null && p1.val > p2.val) { p.next = p2; p2 = p2.next; } else { p.next = p1; p1 = p1.next; } } else { p.next = p2; p2 = p2.next; } } return head.next; }
23. Merge k Sorted Lists
合并 k 个有序链表。思路:借助于堆,堆的大小为 k,先将每个链表的首结点入堆,堆顶元素即为最小值,堆顶出堆后将 next 入堆;依此往复,即可得到整个有序链表。
public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) return null; PriorityQueue minHeap = new PriorityQueue<>(lists.length, new Comparator() { @Override public int compare(ListNode o1, ListNode o2) { return o1.val - o2.val; } }); // initialization for (ListNode node : lists) { if (node != null) minHeap.offer(node); } ListNode head = new ListNode(-1); for (ListNode p = head; !minHeap.isEmpty(); ) { ListNode top = minHeap.poll(); p.next = top; p = p.next; if (top.next != null) minHeap.offer(top.next); } return head.next; }
141. Linked List Cycle
判断链表是否有环。用两个指针,一个快指针一个慢指针,一个每次移动两步,一个每次移动一步;最后两者相遇,即说明有环。
public boolean hasCycle(ListNode head) { if (head == null) return false; for (ListNode slow = head, fast = head; fast.next != null && fast.next.next != null; ) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }
142. Linked List Cycle II
找出链表中环的起始节点 \(s\)。解决思路:用两个指针——fast、slow,先判断是否环;两者第一次相遇的节点与 \(s\) 的距离 == 链表起始节点与 \(s\) 的距离(有兴趣可以证明一下)。
public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) return null; ListNode slow = head, fast = head; boolean isCycled = false; while (slow != null && fast != null && fast.next != null) { // first meeting slow = slow.next; fast = fast.next.next; if (slow == fast) { isCycled = true; break; } } if (!isCycled) return null; for (fast = head; slow != fast;) { // find the cycle start node slow = slow.next; fast = fast.next; } return slow; }
234. Palindrome Linked List
判断链表 \(L\) 是否中心对称。中心对称的充分必要条件:对于任意的 i <= n/2 其中 n 为链表长度,有 L[i] = L[n+1-i] 成立。因此先找出 middle 结点(在距离首结点 n/2 处),然后逆序右半部分链表,与左半部分链表的结点一一比较,即可得到结果。在找出 middle 结点时也用到了小技巧——快慢两个指针遍历链表,当 fast 遍历完成时,slow 即为 middle 结点(证明分 n 为奇偶情况);当 n 为偶数时,middle 结点有两个,此时 slow 为左 middle 结点。换句话说,无论 n 为奇数或偶数,此时的 slow 为右半部分子链表的第一个结点的前驱结点。
public boolean isPalindrome(ListNode head) { if (head == null) return true; ListNode slow = head, fast = head, p; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode q = reverseList(slow.next); // the first node of the right half is `slow.next` for (p = head; q != null; p = p.next, q = q.next) { if (p.val != q.val) return false; } return true; }
143. Reorder List
对于除去首结点外的链表,将右半部分子链表从后往前依次插入进左半部分链表。解决思路与上类似,找出 middle 结点,然后依次插入。值得注意:Java 的对象传参是引用类型,需要更新左半部份子链表的最后一个结点的 next 指针,不然则链表的结点的无限循环导致 OOM。
public void reorderList(ListNode head) { if (head == null || head.next == null) return; ListNode slow = head.next, fast = head.next; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode p, q = reverseList(slow.next); slow.next = null; // update the next pointer of the left half's last node for (p = head; q != null;) { ListNode pNext = p.next, qNext = q.next; p.next = q; // insert qNode into the next of p node q.next = pNext; p = pNext; q = qNext; } }
160. Intersection of Two Linked Lists
求两个链表相交的第一个结点 \(P\)。假定两个链表的长度分别为 m、n,相交的第一个结点 \(P\) 分别距离两个链表的首结点为 a、b,则根据链表相交的特性:两个链表的尾节点都是同一个,即 m-a = n-b;移项后有 m+b = n+a。根据上述性质,在遍历完第一个链表后,再往右 b 个结点,即到达了结点 \(P\)。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode ptrA = headA, ptrB = headB; while (ptrA != ptrB) { // in case ptrA == ptrB == null ptrA = (ptrA != null) ? ptrA.next: headB; ptrB = (ptrB != null) ? ptrB.next: headA; } return ptrA; }
2. Add Two Numbers
模拟两个链表的加法。开始的时候没理解清楚题意,被坑了多次 WA。链表的 head 表示整数的个位,则应从首端对齐开始做加法。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = new ListNode(-1); boolean carry = false; // mark whether has carry for (ListNode p = l1, q = l2, r = head; p != null || q != null || carry; r = r.next) { int pVal = (p == null) ? 0 : p.val; int qVal = (q == null) ? 0 : q.val; int sum = carry ? pVal + qVal + 1 : pVal + qVal; carry = sum >= 10; r.next = new ListNode(sum % 10); if (p != null) p = p.next; if (q != null) q = q.next; } return head.next; }
445. Add Two Numbers II
与上一题不同的是,链表的 head 表示整数的最高位,则应是尾端对齐相加。为了尾端对齐,将采用 stack 来逆序链表,之后相加步骤与上类似;但创建新链表应使用头插法。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode p; Stack s1 = new Stack<>(); Stack s2 = new Stack<>(); for (p = l1; p != null; p = p.next) { s1.push(p.val); } for (p = l2; p != null; p = p.next) { s2.push(p.val); } ListNode head = new ListNode(-1); boolean carry = false; // mark whether has carry for (ListNode r = null; !s1.isEmpty() || !s2.isEmpty() || carry; ) { int pVal = (s1.isEmpty()) ? 0 : s1.pop(); int qVal = (s2.isEmpty()) ? 0 : s2.pop(); int sum = carry ? pVal + qVal + 1 : pVal + qVal; carry = sum >= 10; ListNode node = new ListNode(sum % 10); node.next = r; head.next = node; r = node; } return head.next; }
来源: