链表基础

反转链表

206. 反转链表

92. 反转链表 II

剑指 Offer 06. 从尾到头打印链表

143. 重排链表

25. K 个一组翻转链表

234. 回文链表

删除节点

剑指 Offer 18. 删除链表的节点

237. 删除链表中的节点

面试题 02.03. 删除中间节点

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

83. 删除排序链表中的重复元素

82. 删除排序链表中的重复元素 II

面试题 02.01. 移除重复节点

203. 移除链表元素

排序链表

147. 对链表进行插入排序

148. 排序链表

合并链表

剑指 Offer 25. 合并两个排序的链表

21. 合并两个有序链表

1669. 合并两个链表

23. 合并K个升序链表

分割链表

    1. 分隔链表和面试题 02.04. 分割链表：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
    1. 分隔链表：给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

链表与数学

2. 两数相加

反向存放、反向输出。

面试题 02.05. 链表求和

与上一题相比，有更多的边界条件。

445. 两数相加 II

正向存放，正向输出。

相交链表的题

注明：这三题可以用同一个代码，大家可以自行揣摩题目的区别，反正代码是没啥区别。

    1. 相交链表
  2. 剑指 Offer 52. 两个链表的第一个公共节点
  3. 面试题 02.07. 链表相交

环形链表

    1. 环形链表：判断有没有环
    1. 环形链表 II：返回链表开始入环的第一个节点
  3. 面试题 02.08. 环路检测：跟上题一样

倒数第k个节点

注明：都是用快慢指针法

  1. 剑指 Offer 22. 链表中倒数第k个节点：返回的是节点
  2. 面试题 02.02. 返回倒数第 k 个节点：返回的是节点的值（val）

题解

  • 24 Swap Nodes in Pairs
    • before->p1->p2->head.
  • 25 Reverse Nodes in k-Group
    • Similar to swap nodes in pairs, but do reverse instead of swap.
  • 61 Rotate List
  • 82 Remove Duplicates from Sorted List II
  • 109 Covert Sorted List to Binary Search Tree
    • Converted a sorted linked list into a balanced BST.
  • 138 Copy List with Random Pointer
    • O(1) space in 3 steps: 1) merge two lists into one and set random pointers in new nodes 2) walk list and modify random nodes 3) split list into origin lists.
  • 141 Linked List Cycle
  • 142 Linked List Cycle II
    • O(n) time and O(1) space achieved by Floyd’s circle finding algorithm.
  • 143 Reorder List
    • L(1)->L(2)->…->L(n-1)->L(n) => L(1)->L(n)->L(2)->L(n-1)…
    • O(n) time and O(1) space. Reverse the second half and merge.
  • 147 Insertion Sort List
  • 206 Reverse Linked List
  • 328 Odd Even Linked List
    • L(1)->L(2)->…->L(n-1)->L(n) => L(1)->L(3)->…L(2)->L(4)…
    • O(n) time and in place. Invariant: odd-even list + origin list.
  • 369 Plus One Linked List
  • 430 Flatten a Multilevel Doubly Linked List
    • Preorder traversal.
  • 708 Insert into a Cyclic Sorted List
    • First find min/max of linked list. Then find max-min or some increasing tuple.

参考资料