- Published on
链表
- Authors
- Name
- Eric Yuan
- @EricYuansz
链表
class Node<V> {
V value;
Node next;
}
class Node<V> {
V value;
Node next;
Node last;
}
对于链表算法，在面试中，一定尽量用到空间复杂度最小的方法（不然凭啥用咱是吧 🐶）。
链表「换头」情况
操作链表出现「换头」的情况，函数的递归调用形式应该是 head = func(head.next)，所以函数在设计的时候就应该有一个 Node 类型的返回值，比如反转链表。
哨兵守卫
「哨兵守卫」是链表中的常用技巧。通过在链表头部或尾部添加守卫节点，可以简化对边界情况的处理。
链表中常用的技巧-快慢指针
找到链表的中点、中点前一个、中点后一个
这个是硬编码能力，需要大量练习打好基本功。
/**
* 奇数的中点; 偶数的中点靠前一位
*/
Node s = head;
Node f = head;
while (f.next != null && f.next.next != null) {
s = s.next;
f = f.next.next;
}
/**
* 奇数的中点; 偶数的中点靠后一位 lc.876 easy
*/
while (f != null && f.next != null) {
s = s.next;
f = f.next.next;
}
如果要进一步继续偏移，修改 f 或 s 的初始节点即可。
注意：因为 f 一次走两步，所以：
- 想要获取中点往前的节点，修改 f 初始节点时
f=head.next.next，两个 next 才会让结果往前偏移一步 - 想要获取中点往后的节点，修改 s 的初始节点
s=head.next，一个 next 就可以让结果往后偏移一步
练习
lc.2 两数相加
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
let dummy = new ListNode(-1)
let p = dummy
let p1 = l1,
p2 = l2
let carry = 0
while (p1 || p2) {
let a = p1 ? p1.val : 0
let b = p2 ? p2.val : 0
let sum = a + b + carry
carry = (sum / 10) | 0
p.next = new ListNode(sum % 10)
p = p.next
p1 = p1 ? p1.next : null
p2 = p2 ? p2.next : null
}
if (carry) {
p.next = new ListNode(carry)
}
return dummy.next
}
lc.19 删除链表倒数第 N 个节点
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
let p = head
while (n--) {
p = p.next
}
let dummy = new ListNode(-1, head)
let p2 = dummy
while (p) {
p = p.next
p2 = p2.next
}
p2.next = p2.next.next
return dummy.next
}
lc.2 和 lc.19 是 dummy 守卫节点的最佳实践了，一个是新增，一个是删除。
lc.21 合并两个有序链表 easy
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function (list1, list2) {
let dummy = new ListNode(-1)
let p = dummy
let p1 = list1,
p2 = list2
while (p1 && p2) {
if (p1.val < p2.val) {
p.next = p1
p1 = p1.next
} else {
p.next = p2
p2 = p2.next
}
p = p.next
}
if (p1) p.next = p1
if (p2) p.next = p2
return dummy.next
}
lc.23 合并 K 个有序链表 hard
这道题比较朴素的做法是：已知两个有序链表的合并，那么遍历所有链表逐条合并即可。
性能强一点的做法是利用优先队列。JS 中没有，得先手动实现；Java 中有 PQ，得设置比较函数。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
let dummy = new ListNode(-1)
let p = dummy
lists = lists.filter((item) => item !== null)
const pq = new PQ(lists, (a, b) => a > b)
while (!pq.isEmpty()) {
const top = pq.pop()
p.next = top
p = p.next
if (top && top.next) {
pq.push(top.next)
}
}
return dummy.next
}
/** 手动实现优先队列 */
class PQ {
constructor(data, comparator) {
this.data = data
this.comparator = comparator
for (let i = data.length >> 1; i >= 0; --i) this.down(i)
}
up(i) {
while (i > 0 && this.comparator(this.data[(i - 1) >> 1].val, this.data[i].val)) {
this.swap((i - 1) >> 1, i)
i = (i - 1) >> 1
}
}
down(i) {
let left = 2 * i + 1
while (left < this.data.length) {
let min = left
if (left + 1 < this.data.length) {
min = this.comparator(this.data[left + 1].val, this.data[left].val) ? left : left + 1
}
min = this.comparator(this.data[i].val, this.data[min].val) ? i : min
if (min === i) break
this.swap(min, i)
i = min
left = 2 * i + 1
}
}
push(val) {
this.up(this.data.push(val) - 1)
}
pop() {
this.swap(0, this.data.length - 1)
const top = this.data.pop()
this.down(0)
return top
}
swap(i, j) {
const temp = this.data[i]
this.data[i] = this.data[j]
this.data[j] = temp
}
isEmpty() {
return this.data.length === 0
}
}
另一种递归解：归并
var mergeKLists = function (lists) {
if (lists.length === 0) return null
if (lists.length === 1) return lists[0]
const mid = lists.length >> 1
const left = mergeKLists(lists.slice(0, mid))
const right = mergeKLists(lists.slice(mid))
return mergeTwoList(left, right)
}
function mergeTwoList(a, b) {
if (!a) return b
if (!b) return a
if (a.val < b.val) {
a.next = mergeTwoList(a.next, b)
return a
} else {
b.next = mergeTwoList(a, b.next)
return b
}
}
lc.24 两两交换链表中的节点
不错的一道题
var swapPairs = function (head) {
if (head === null || head.next === null) return head
const newHead = head.next // cache
head.next = swapPairs(head.next.next)
newHead.next = head // 归 - 后序位置
return newHead
}
/** 迭代解法 */
var swapPairs = function (head) {
const dummy = new ListNode(-1)
dummy.next = head
let p = dummy
while (p.next !== null && p.next.next !== null) {
const a = p.next // cache
const b = p.next.next // cache
p.next = b
a.next = b.next
b.next = a
p = a
}
return dummy.next
}
可以看见，无论是递归还是迭代，因为要变动后方的节点，所以一般都可以先做一层缓存。
lc.83 删除链表的重复元素 easy
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function (head) {
let p = head
while (p && p.next) {
if (p.val === p.next.val) {
p.next = p.next.next
} else {
p = p.next
}
}
return head
}
单链表分区
在三路快排中，有类似的操作。所以如果借助数组，那么就是荷兰国旗问题了。
但是这样做时间复杂度就高了，对于链表，能用指针操作的，就不借助额外空间。要想空间复杂度为 O(1)，那么就得借助 6 个变量 <head <tail; =head =tail; >head >tail。
lc.86 分隔链表
这道题是上方分区的简化版本，只用把小于 X 的节点放到大于等于 X 的节点之前即可。
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function (head, x) {
if (head === null || head.next === null) return head
let small = new ListNode(-1)
let large = new ListNode(-1)
let p = head,
p1 = small,
p2 = large
while (p !== null) {
const val = p.val
if (val < x) {
p1.next = p
p1 = p1.next
} else {
p2.next = p
p2 = p2.next
}
p = p.next
}
p2.next = null // 注意需要给大的收尾~
p1.next = large.next
return small.next
}
lc.138 复制含有随机指针的链表
/**
* Java版本：这道题要是空间复杂度不需要 O(1)，那么用哈希表就挺好做的
*
* O(1) 的空间复杂度，就需要一定的技巧了，就是 拼接+拆分。
*/
// 哈希表
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node p = head;
while (p != null) {
map.put(p, new Node(p.val));
p = p.next;
}
p = head;
while(p != null) {
map.get(p).next = map.get(p.next);
map.get(p).random = map.get(p.random);
p = p.next;
}
return map.get(head);
}
}
/** 空间复杂度 O(1) */
public Node copyRandomList(Node head) {
// 恰到好处的拼接，复制节点直接拼到原节点后，这样会发现：
// ** 新节点的random指向的就是原节点random指向节点的下一个节点 **
// 1.复制节点
Node p = head;
while (p != null) {
Node newNode = new Node(p.val);
newNode.next = p.next;
p.next = newNode;
p = newNode.next;
}
// 2.设置 random
p = head;
while (p != null) {
if(p.random != null) {
p.next.random = p.random.next;
}
p = p.next.next;
}
// 3. 分离链表
Node dummy = new Node(-1);
p = head;
Node curr = dummy;
while (p != null) {
curr.next = p.next;
curr = curr.next;
p.next = curr.next;
p = p.next;
}
return dummy.next;
}
/**
* // Definition for a Node.
* function Node(val, next, random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/
/**
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function (head) {
/** 尽可能降低空间复杂度，使用拼接技巧 */
let p = head
while (p !== null) {
const cpNode = new Node(p.val)
cpNode.next = p.next
p.next = cpNode
p = cpNode.next
}
p = head
while (p !== null) {
if (p.random) {
p.next.random = p.random.next
}
p = p.next.next
}
const dummy = new Node(-1)
let curr = dummy
p = head
while (p !== null) {
curr.next = p.next
curr = curr.next
p.next = curr.next
p = p.next
}
return dummy.next
}
单链表环相关问题
快慢指针判断是否有环的原理是：如果有环，则必定两个指针会相遇；否则，快指针将走到空。
lc.141 判断链表是否有环 easy
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
if (head == null) return false
let f = head.next,
s = head
while (true) {
if (f == null || f.next == null) return false
s = s.next
f = f.next.next
if (s === f) return true
}
// 下面那种写法也行
// if (head == null) return false
// let s = head,
// f = head.next // !!! 注意这里是先走了一步的
// while (s !== f) {
// if (f == null || f.next == null) return false
// s = s.next
// f = f.next.next
// }
// return true
}
lc.142 返回环的起点
此题应用的是著名的 Floyd 判圈算法（维基百科）。应用快慢指针，第一次相遇后快指针回到头部和慢指针一起走，再次相遇就是环的起点。
假设 head 到环起点的距离为 a，环起点到快慢指针相遇的距离为 b，环长度为 c ，则：
- 慢指针走了 a + b，
- 快指针走了 a + b + n*c， n 为圈数
第一次相遇时，慢指针走 k，快指针走 2k，快比慢多走了 k 步，所以 n * c = k，因此 k 是环的整数倍。所以回到起点的指针要再走 k - b 步才到起点，而从第一次相遇点走到环起点的距离也恰好也为 k - b。
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
if (head === null || head.next === null) return null
let s = head,
f = head
while (true) {
if (f == null || f.next == null) return null
s = s.next
f = f.next.next
if (s === f) break
}
f = head
while (s !== f) {
f = f.next
s = s.next
}
return s
}
单链表相交问题
处理链表相交一类的问题，核心在于 「抹除长度差异」，然后齐头并进，有相等节点则相交。
lc.160 相交链表 easy
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
if (headA == null || headB == null) return null
let n = 0
let p1 = headA,
p2 = headB // 假定 p1 为长，p2 为 短
while (p1 !== null) {
n++
p1 = p1.next
}
while (p2 !== null) {
n--
p2 = p2.next
}
if (n > 0) {
p1 = headA
p2 = headB
} else {
p1 = headB
p2 = headA
}
n = Math.abs(n)
while (n--) {
p1 = p1.next
}
while (p1 !== p2) {
p1 = p1.next
p2 = p2.next
}
return p1
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode l = headA, s = headB;
int n = 0;
while (l != null) {
n++;
l = l.next;
}
while (s != null) {
n--;
s = s.next;
}
if (l != s) return null;
l = n > 0 ? headA : headB;
s = n > 0 ? headB : headA;
n = Math.abs(n);
while (n != 0) {
l = l.next;
n--;
}
while (l != s) {
l = l.next;
s = s.next;
}
return l;
}
}
有个取巧的小技巧是，当两个指针第一次走到末尾后，分别跳到对方链表上去，这样等价于抹除了长度差异，如有相交，则会走到相同节点上。具体见官解。
进阶：有环单链表相交
/**
* 有环单链表相交要分清楚情况：
* 1. 不相交
* 2. 环的起始节点一样，则把这个起始节点看成两个无环链表的终点，利用上题的解法求出相交节点即可
* 3. 环的起始节点不一样，则这两个节点都是相交节点，返回任意一个即可
*
* 1 和 3 情况的区分是，一个环的节点继续走，走回自己之前能遇到另一个环的节点就是情况3，否则就是情况1
*/
public ListNode bothLoop(ListNode head1, ListNode head2, ListNode loop1, ListNode loop2) {
/**
* 第 2 种情况，两个有环链表共用环起点，
* 那么此时可以把环的起点看成是head1和head2到的无环链表的终点，
* 也就转化成了寻找两个无环单链表相交点的问题了。
*/
if (loop1 == loop2) {
ListNode p1 = head1, p2 = head2;
int n = 0;
while (p1 != loop1) {
n++;
p1 = p1.next;
}
while (p2 != loop2) {
n--;
p2 = p2.next;
}
p1 = n > 0 ? head1 : head2;
p2 = n > 0 ? head2 : head1;
n = Math.abs(n);
while (n > 0) {
p1 = p1.next;
n--;
}
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
} else {
/**
* 第 1 种情况不相交和第 3 种情况相交在环上不同的节点
* 区分方式是让节点从 loop1 开始继续绕环走，能遇到 loop2 则说明相交了，否则为不相交
*/
ListNode p = loop1.next; // 先前进一步，否则while进不去喽～
while (p != loop1) {
if (p == loop2) {
return loop2; // loop1 loop2都是相交点，随意返回一个
}
p = p.next;
}
return null;
}
}
反转链表问题
lc.206 反转链表 hot easy
最基本的考验对双指针和递归的理解。不错的一道经典题。
// 迭代法，那就是双指针了，先存储后继节点，剩下的都好办
public ListNode reverseList(ListNode head) {
ListNode p = head, pre = null;
while(p != null) {
ListNode next = p.next; // 储存后继节点
p.next = pre;
pre = p;
p = next;
}
return pre;
}
// 递归法
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next); // newHead 是最后一个节点
// 后序遍历，假设递归到最后了，此时的 head 是最后一个节点的前一个节点
head.next.next = head; // 把下一个节点的next指向自身
head.next = null; // 把自身的next指向null
return newHead; // 返回尾部节点的引用指针即可
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
if (!head || !head.next) return head
const newHead = reverseList(head.next)
head.next.next = head
head.next = null
return newHead
}
var reverseList = function (head) {
let p = head,
pre = null
while (p) {
const next = p.next
p.next = pre
pre = p
p = next
}
return pre
}
lc.92 反转链表 II
如果不要求只一次遍历，利用 lc.206 就可以完成了。
只能遍历一次的话，需要技巧，就是每遍历到反转区间内的一个元素，就把这个元素放到反转区间的头部。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function (head, left, right) {
const dummy = new ListNode(-1) // left 可能为头，守卫简化操作
dummy.next = head
let p = dummy
for (let i = 0; i < left - 1; ++i) {
p = p.next
}
// 此时，p 指向区间的前一个节点
const len = right - left + 1
let curr = p.next
let step = len - 1
while (step--) {
const next = curr.next
curr.next = next.next
next.next = p.next
p.next = next
}
return dummy.next
}
lc.25 K 个一组反转链表 hard
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function (head, k) {
if (head === null) return head
let a = (b = head)
for (let i = 0; i < k; ++i) {
if (b == null) return head // 不足 k
b = b.next
}
const newHead = reverse(a, b)
a.next = reverseKGroup(b, k) // [a, b) 反转后 a 的 next 为剩下的链表反转
return newHead
}
/**
* 反转 [head, tail) 区间的链表，其实普通的反转链表反转的就是 [head, null) 区间罢了
*/
function reverse(head, tail) {
let prev = null,
curr = head
while (curr !== tail) {
const next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}
lc.234 回文链表 easy
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
if (head === null) return false
let s = head,
f = head
while (f !== null && f.next !== null) {
s = s.next
f = f.next.next
}
// 对后半部分， s 进行反转
let prev = null
while (s !== null) {
const next = s.next
s.next = prev
prev = s
s = next
}
// 对 prev 和 head 进行比较
while (prev) {
if (prev.val !== head.val) return false
prev = prev.next
head = head.next
}
return true
}
插入一下Java哈希表的了解
在 javascript 中的 Set 和 Map 咱就不说啥了，非正规军 😄。来看看 java 的：
- 无序表
- HashSet: add remove contains，对呀 c++ 中的 unordered_set
- HashMap: put remove containsKey，对应 c++ 中的 unordered_map
- 有序表
- TreeSet：它是按升序对元素进行排序，对应 c++ 中的 ordered_set
- TreeMap：基于红黑树的 NavigableMap 实现，它根据其键的自然顺序排序，对应 c++ 中的 ordered_map
记得之前学 java 的时候， HashSet 底层就是 HashMap，只不过没有 value 只有 key 罢了，而常规的 HashMap 的底层则是 链表，在 java 中，当链表的长度到达 8 时，就会自动扩容，链表也会重新分配，好像有红黑树什么的（不清楚，后序学习再回头补充），后面了解到哈希函数的时候，就更加清楚了，离散函数使得分配空间时基本是离散均匀的。
- 放入无/有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
- 放入无序表的东西，如果不是基础类型，内部按引用传递，内存占用的就是这个东西的内存地址的大小，java 中是 8 个字节
- 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递...。
重点：无序表 的增删改查的时间复杂度都是 常数 级别（比较大的常数 哈哈），有序表的时间复杂度都是 O(logn) 级别