基本概念 #
单向链表 #
JavaScript #
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
Golang #
type ListNode struct {
Val int
Next *ListNode
}
双向链表 #
双向链表在单向链表节点的基础上增加了指向前一个节点的指针，这样一来，既可以从头节点开始从前往后遍历到尾节点，也可以从尾节点开始从后往前遍历到头节点。
环形链表 #
如果把链表尾节点指向下一个节点的指针指向链表的头节点，那么此时链表就变成一个环形链表（也叫循环链表），相当于链表的所有节点都位于一个环中。环形链表既可以是单向链表也可以是双向链表。
142. 环形链表 II（链表中环的入口节点）✅
环形链表优先考虑用快慢指针解决。
有序链表 #
83. 删除排序链表中的重复元素 需要将 pre 节点和 curr 节点做比较。
相交链表 #
回文链表 #
234. 回文链表 解法有：
- 将值复制到数组用前后双指针对比。
- 递归，参考反转链表的递归思路。
- 入栈和出栈。
链表操作 #
一般使用一个哨兵结点来进行链表的遍历。
void addLast(int x) {
if (first == null) { //需要判断头节点是否存在
first = new Node(x, null);
return;
}
Node p = first;
while (p.next != null) { //如果头结点存在，则不断的找到尾节点，并将当前的节点添加至尾部
p = p.next;
}
p.next = new Node(x, null);
}
插入元素 #
删除元素 #
遍历链表 #
反转链表 #
206. 反转链表 感觉是个必须得会的题。。
看到题目基本能知道有两种思路，一种是按顺序遍历链表，逐个更新 next 结点，另一种就是利用递归入栈，从最后一个结点开始反向出栈更新 next。
方法一：迭代
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil{
return head
}
var prev *ListNode
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
方法二：递归
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
last := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return last
}
进阶练习 92. 反转链表 II ✅
旋转链表 #
思路：
- 简化 k 的旋转计算
- 将链表闭合为环
- 旋转 K 下即为头节点的
next迭代次数。 - 找到头节点，将环分开。
合并链表 #
递归解法
var mergeTwoLists = function(l1, l2) {
if (l1 === null) {
return l2;
} else if (l2 === null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};
迭代解法
需要一个哑结点 dummy，最后返回 dummy.next 即可。
var mergeTwoLists = function(list1, list2) {
let dummy = new ListNode(0)
let prev = dummy
while(list1 !== null && list2 !== null) {
if (list1.val < list2.val) {
prev.next = list1
list1 = list1.next
} else {
prev.next = list2
list2 = list2.next
}
prev = prev.next
}
if (list1 === null) {
prev.next = list2
} else {
prev.next = list1
}
return dummy.next
};
方法技巧 #
快慢指针 #
快慢指针方法也被称为 Hare & Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。
设两个指针，fast 和 slow，fast 指针每次移动两格， slow 指针每次移动一格， 如果存在环路， 则 fast 最终一定会和 slow 相遇。
var hasCycle = function(head) {
let fast = head
let slow = head
while(fast !== null) {
fast = fast.next
if (fast !== null) {
fast = fast.next
}else {
return false
}
slow = slow.next
if (slow === fast) {
return true
}
}
return false
};
哑结点（虚拟头） #
当需要对头结点操作时，可以考虑使用哑结点（dummy node），即创建一个新的结点，并使 dummy.next = head 指向头结点，这样可以避免处理头结点为空的边界问题。
可以参考下面 前后指针 19. 删除链表的倒数第 N 个结点 这个题。
前后指针 #
前后指针区别于快慢指针，两个指针步伐通常一致。
var removeNthFromEnd = function(head, n) {
let tail = head
let dummy = new ListNode(0, head)
let prev = dummy
for (let i = 0; i < n; i ++) {
tail = tail.next
}
while (tail !== null) {
tail = tail.next
prev = prev.next
}
prev.next = prev.next.next
return dummy.next
};