数据结构与算法-链表
一、删除去重
203. 移除链表元素
用虚拟头节点统一处理头节点删除。指针始终停在待检查节点的前驱：后继值等于目标值就跳过，否则前进一步；删除后不移动前驱，才能连续删除多个目标节点。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
func removeElements(head *ListNode, val int) *ListNode {
dummy := &ListNode{Next: head}
cur := dummy
for cur.Next != nil {
if cur.Next.Val == val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return dummy.Next
}
83. 删除排序链表中的重复元素
链表已经有序，相同值一定相邻。比较当前节点与后继，相等就跳过后继，不相等再前进；每个值保留一个节点。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == cur.val) {
// 跳过重复节点，cur 原地不动继续检查新的后继。
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
func deleteDuplicates(head *ListNode) *ListNode {
cur := head
for cur != nil && cur.Next != nil {
if cur.Next.Val == cur.Val {
// 跳过重复节点，cur 原地不动继续检查新的后继。
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
82. 删除排序链表中的重复元素 II
与 83 不同，重复值对应的节点要整段删除。用虚拟头节点和前驱指针记录已保留部分，先走完相同值的一段，再决定跨过整段还是保留单个节点。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
boolean isDuplicate = false;
while (cur.next != null && cur.next.val == cur.val) {
cur = cur.next;
isDuplicate = true;
}
if (isDuplicate) {
// 整段重复值一个不留。
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
}
func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre, cur := dummy, head
for cur != nil {
isDuplicate := false
for cur.Next != nil && cur.Next.Val == cur.Val {
cur = cur.Next
isDuplicate = true
}
if isDuplicate {
// 整段重复值一个不留。
pre.Next = cur.Next
} else {
pre = cur
}
cur = cur.Next
}
return dummy.Next
}
面试题 02.01. 移除重复节点
无序链表不能依靠相邻比较去重。用哈希集合记录已保留的值，遇到重复值就修改前驱的后继跳过该节点，保留每个值第一次出现的位置。
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
if (head == null) {
return null;
}
Set<Integer> seen = new HashSet<>();
seen.add(head.val);
ListNode pre = head;
while (pre.next != null) {
if (seen.add(pre.next.val)) {
pre = pre.next;
} else {
// 值已出现，删掉后继节点。
pre.next = pre.next.next;
}
}
return head;
}
}
func removeDuplicateNodes(head *ListNode) *ListNode {
if head == nil {
return nil
}
seen := map[int]bool{head.Val: true}
pre := head
for pre.Next != nil {
if seen[pre.Next.Val] {
// 值已出现，删掉后继节点。
pre.Next = pre.Next.Next
} else {
seen[pre.Next.Val] = true
pre = pre.Next
}
}
return head
}
237. 删除链表中的节点
题目只给待删除节点，且保证它不是尾节点，无法找到前驱。把后继节点的值复制到当前节点，再跳过后继，以达到删除当前值的效果；这种做法不适用于删除尾节点。
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
func deleteNode(node *ListNode) {
node.Val = node.Next.Val
node.Next = node.Next.Next
}
二、链表反转
206. 反转链表
用前驱、当前节点和临时后继三个指针迭代反转。每次先保存原后继，再把当前节点指向前驱，最后整体前进；遍历结束后前驱就是新头。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
92. 反转链表 II
先定位反转区间的前驱，反转指定数量的节点，再把原区间头接到右侧剩余链表，区间前驱接到新头。虚拟头节点可以统一处理反转从第一个节点开始的情况。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head);
ListNode preLeft = dummy;
for (int i = 1; i < left; i++) {
preLeft = preLeft.next;
}
ListNode cur = preLeft.next;
ListNode pre = null;
for (int i = left; i <= right; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 原区间头（现在的区间尾）接 right 的后继，前驱接区间新头。
preLeft.next.next = cur;
preLeft.next = pre;
return dummy.next;
}
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummy := &ListNode{Next: head}
preLeft := dummy
for i := 1; i < left; i++ {
preLeft = preLeft.Next
}
cur := preLeft.Next
var pre *ListNode
for i := left; i <= right; i++ {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 原区间头（现在的区间尾）接 right 的后继，前驱接区间新头。
preLeft.Next.Next = cur
preLeft.Next = pre
return dummy.Next
}
24. 两两交换链表中的节点 ❤️
每次取出相邻两个节点，通过修改前驱、第一节点、第二节点之间的连接完成交换，再把前驱移到这一组的新尾。只交换指针，不交换节点值，末尾不足两个节点时保持原样。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode first = pre.next;
ListNode second = first.next;
// 三步换指针，顺序不能乱。
first.next = second.next;
second.next = first;
pre.next = second;
pre = first;
}
return dummy.next;
}
}
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre := dummy
for pre.Next != nil && pre.Next.Next != nil {
first := pre.Next
second := first.Next
// 三步换指针，顺序不能乱。
first.Next = second.Next
second.Next = first
pre.Next = second
pre = first
}
return dummy.Next
}
25. K 个一组翻转链表 ❤️
先统计长度，只处理剩余长度不少于 k 的完整分组。每组反转 k 个节点后，将上一组尾接到本组新头，本组原头接到下一组；不足 k 个节点的尾段不反转。
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
length++;
}
ListNode dummy = new ListNode(0, head);
ListNode preGroupEnd = dummy;
while (length >= k) {
ListNode cur = preGroupEnd.next;
ListNode groupStart = cur;
ListNode pre = null;
for (int i = 0; i < k; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 原组头反转后变组尾，接下一组起点；上一组尾接新组头。
preGroupEnd.next = pre;
groupStart.next = cur;
preGroupEnd = groupStart;
length -= k;
}
return dummy.next;
}
}
func reverseKGroup(head *ListNode, k int) *ListNode {
length := 0
for cur := head; cur != nil; cur = cur.Next {
length++
}
dummy := &ListNode{Next: head}
preGroupEnd := dummy
for length >= k {
cur := preGroupEnd.Next
groupStart := cur
var pre *ListNode
for i := 0; i < k; i++ {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 原组头反转后变组尾，接下一组起点；上一组尾接新组头。
preGroupEnd.Next = pre
groupStart.Next = cur
preGroupEnd = groupStart
length -= k
}
return dummy.Next
}
三、拆分与拼接
86. 分隔链表
按节点值是否小于 x 分到两条链，分别用尾指针追加以保持原有顺序。最后把小值链接到大值链，并将大值链尾置空，防止旧连接形成环。
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallDummy = new ListNode();
ListNode largeDummy = new ListNode();
ListNode small = smallDummy;
ListNode large = largeDummy;
for (ListNode cur = head; cur != null; cur = cur.next) {
if (cur.val < x) {
small.next = cur;
small = small.next;
} else {
large.next = cur;
large = large.next;
}
}
// 断尾，防止成环。
large.next = null;
small.next = largeDummy.next;
return smallDummy.next;
}
}
func partition(head *ListNode, x int) *ListNode {
smallDummy := &ListNode{}
largeDummy := &ListNode{}
small, large := smallDummy, largeDummy
for cur := head; cur != nil; cur = cur.Next {
if cur.Val < x {
small.Next = cur
small = small.Next
} else {
large.Next = cur
large = large.Next
}
}
// 断尾，防止成环。
large.Next = nil
small.Next = largeDummy.Next
return smallDummy.Next
}
328. 奇偶链表
按节点位置的奇偶拆链，不是按节点值的奇偶。分别维护奇数位置链和偶数位置链，保存偶数链头，拆分完成后将奇数链尾接到偶数链头。
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return null;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
func oddEvenList(head *ListNode) *ListNode {
if head == nil {
return nil
}
odd := head
even := head.Next
evenHead := even
for even != nil && even.Next != nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
odd.Next = evenHead
return head
}
725. 分隔链表
先统计总长度，每段至少分到
length / k个节点，前length % k段各多一个。逐段走到尾部后断开连接；节点数小于 k 时，后面的部分为空链表。
class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
length++;
}
int partSize = length / k;
// 前 extra 段各多一个节点。
int extra = length % k;
ListNode[] res = new ListNode[k];
ListNode cur = head;
for (int i = 0; i < k && cur != null; i++) {
res[i] = cur;
int size = partSize + (i < extra ? 1 : 0);
for (int j = 1; j < size; j++) {
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return res;
}
}
func splitListToParts(head *ListNode, k int) []*ListNode {
length := 0
for cur := head; cur != nil; cur = cur.Next {
length++
}
partSize := length / k
// 前 extra 段各多一个节点。
extra := length % k
res := make([]*ListNode, k)
cur := head
for i := 0; i < k && cur != nil; i++ {
res[i] = cur
size := partSize
if i < extra {
size++
}
for j := 1; j < size; j++ {
cur = cur.Next
}
next := cur.Next
cur.Next = nil
cur = next
}
return res
}
61. 旋转链表
统计长度并将 k 对长度取模。先把首尾连成环，再定位新尾、记录新头并断开环；空链表、单节点以及旋转量为长度整数倍时直接返回。
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
int length = 1;
ListNode tail = head;
while (tail.next != null) {
length++;
tail = tail.next;
}
k %= length;
if (k == 0) {
return head;
}
// 成环后从原尾走 length - k 步到新尾。
tail.next = head;
for (int i = 0; i < length - k; i++) {
tail = tail.next;
}
ListNode newHead = tail.next;
tail.next = null;
return newHead;
}
}
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
length := 1
tail := head
for tail.Next != nil {
length++
tail = tail.Next
}
k %= length
if k == 0 {
return head
}
// 成环后从原尾走 length - k 步到新尾。
tail.Next = head
for i := 0; i < length-k; i++ {
tail = tail.Next
}
newHead := tail.Next
tail.Next = nil
return newHead
}
1669. 合并两个链表
分别定位被替换区间之前的节点和区间之后的节点，将前者接到 list2 的头，再把 list2 的尾接到后者。重点是区分前驱、区间末尾和末尾后继，避免位置偏一。
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode dummy = new ListNode(0, list1);
ListNode preA = dummy;
ListNode afterB = dummy;
for (int i = 0; i < a; i++) {
preA = preA.next;
}
for (int i = 0; i < b + 2; i++) {
afterB = afterB.next;
}
preA.next = list2;
ListNode tail = list2;
while (tail.next != null) {
tail = tail.next;
}
tail.next = afterB;
return dummy.next;
}
}
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
dummy := &ListNode{Next: list1}
preA, afterB := dummy, dummy
for i := 0; i < a; i++ {
preA = preA.Next
}
for i := 0; i < b+2; i++ {
afterB = afterB.Next
}
preA.Next = list2
tail := list2
for tail.Next != nil {
tail = tail.Next
}
tail.Next = afterB
return dummy.Next
}
四、双指针
876. 链表的中间结点
快指针每次走两步，慢指针每次走一步。快指针到达末尾时慢指针位于中点；两者从头节点同时出发，偶数长度时返回靠后的中间节点。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
func middleNode(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
19. 删除链表的倒数第 N 个结点
用虚拟头节点处理删除头节点的情况。快指针先走 n + 1 步，再与慢指针同步前进；快指针为空时，慢指针恰好位于倒数第 n 个节点的前驱，修改一次连接即可删除。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy;
ListNode slow = dummy;
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
fast := dummy
slow := dummy
for i := 0; i <= n; i++ {
fast = fast.Next
}
for fast != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
2095. 删除链表的中间节点
快指针从头节点出发、慢指针从虚拟头节点出发，两者分别走两步和一步。结束时慢指针停在中间节点的前驱；单节点链表也能通过同一次跳过操作返回空链表。
class Solution {
public ListNode deleteMiddle(ListNode head) {
// 哨兵让 slow 有一个链表外的起点，从根上消除「删头节点」的特判。
ListNode dummy = new ListNode(0, head);
// slow 起点比 fast 早一格，因此终点也早一格，落在待删节点的前驱上。
ListNode slow = dummy;
ListNode fast = head;
while (fast != null && fast.next != null) {
// 不变量：fast 走 2k 步时 slow 走 k 步。
slow = slow.next;
fast = fast.next.next;
}
// slow 是下标 ⌊n/2⌋ 节点的前驱，直接跨过待删节点。
slow.next = slow.next.next;
// 头节点可能已被删除，必须返回 dummy.next 而不是 head。
return dummy.next;
}
}
func deleteMiddle(head *ListNode) *ListNode {
// 哨兵让 slow 有一个链表外的起点，从根上消除「删头节点」的特判。
dummy := &ListNode{Next: head}
// slow 起点比 fast 早一格，因此终点也早一格，落在待删节点的前驱上。
slow, fast := dummy, head
for fast != nil && fast.Next != nil {
// 不变量：fast 走 2k 步时 slow 走 k 步。
slow = slow.Next
fast = fast.Next.Next
}
// slow 是下标 ⌊n/2⌋ 节点的前驱，直接跨过待删节点。
slow.Next = slow.Next.Next
// 头节点可能已被删除，必须返回 dummy.Next 而不是 head。
return dummy.Next
}
141. 环形链表
快指针每次两步、慢指针每次一步。如果有环，两者会在环内相遇；如果快指针先到达空节点，就没有环。比较的是节点身份，而不是节点值。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
func hasCycle(head *ListNode) bool {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
142. 环形链表 II
先用快慢指针找到环内相遇点。相遇后把其中一个指针移回头节点，两个指针都改为每次走一步，再次相遇的位置就是环入口；没有环则返回空节点。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}
func detectCycle(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
fast = head
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
}
return nil
}
160. 相交链表
两个指针分别从两条链的头出发，走到末尾后换到另一条链的头。这样各自走过两条链的长度，消除长度差；最终在同一个公共节点相遇，或同时到达空节点。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while (a != b) {
// 走到尽头就换到另一条链的头，抹平长度差。
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a, b := headA, headB
for a != b {
// 走到尽头就换到另一条链的头，抹平长度差。
if a == nil {
a = headB
} else {
a = a.Next
}
if b == nil {
b = headA
} else {
b = b.Next
}
}
return a
}
五、反转应用
234. 回文链表
先用快慢指针找到中点，再反转后半段，从两端对应位置逐个比较。奇数长度时中间节点不影响回文判断；当前实现会改变后半段连接，若调用方要求保留原链表，需要比较后再恢复。
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转后半段。
ListNode pre = null;
ListNode cur = slow;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode left = head;
ListNode right = pre;
while (right != null) {
if (left.val != right.val) {
return false;
}
left = left.next;
right = right.next;
}
return true;
}
}
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 反转后半段。
var pre *ListNode
cur := slow
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
left, right := head, pre
for right != nil {
if left.Val != right.Val {
return false
}
left = left.Next
right = right.Next
}
return true
}
143. 重排链表 ❤️
先找前半段末尾并断开两段，再反转后半段，最后交替连接前半段和反转后的后半段。每次改指针前保存两边的后继，避免丢链或重新形成环。
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
// 快慢指针找中点，slow 停在前半段末尾。
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode cur = slow.next;
slow.next = null;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode p1 = head;
ListNode p2 = pre;
while (p2 != null) {
ListNode next1 = p1.next;
ListNode next2 = p2.next;
p1.next = p2;
p2.next = next1;
p1 = next1;
p2 = next2;
}
}
}
func reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
// 快慢指针找中点，slow 停在前半段末尾。
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
cur := slow.Next
slow.Next = nil
var pre *ListNode
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
p1, p2 := head, pre
for p2 != nil {
next1, next2 := p1.Next, p2.Next
p1.Next = p2
p2.Next = next1
p1 = next1
p2 = next2
}
}
2130. 链表最大孪生和
题目保证链表长度为偶数，快慢指针可以直接定位后半段起点。反转后半段，再与前半段同步遍历，计算每对原本首尾对应节点的和并取最大值；遍历长度以后半段为准。
class Solution {
public int pairSum(ListNode head) {
// 同起点快慢指针：fast 走满 n 步时 slow 恰好走 n/2 步。
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// n 为偶数，slow 精确停在下标 n/2，即后半段的第一个节点。
ListNode prev = null;
while (slow != null) {
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// prev 是原链表的尾节点；比较时只遍历反转后的后半段。
int ans = 0;
while (prev != null) {
// 第 t 轮：head 在下标 t，prev 在下标 n-1-t，正好一对孪生节点。
ans = Math.max(ans, head.val + prev.val);
head = head.next;
prev = prev.next;
}
return ans;
}
}
func pairSum(head *ListNode) int {
// 同起点快慢指针：fast 走满 n 步时 slow 恰好走 n/2 步。
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// n 为偶数，slow 精确停在下标 n/2，即后半段的第一个节点。
var prev *ListNode
for slow != nil {
next := slow.Next
slow.Next = prev
prev = slow
slow = next
}
// prev 是原链表的尾节点；比较时只遍历反转后的后半段。
ans := 0
for prev != nil {
// 第 t 轮：head 在下标 t，prev 在下标 n-1-t，正好一对孪生节点。
if head.Val+prev.Val > ans {
ans = head.Val + prev.Val
}
head = head.Next
prev = prev.Next
}
return ans
}
六、合并与排序
21. 合并两个有序链表
用虚拟头节点和尾指针构造结果链，每次接入两条链中值较小的头节点，再移动对应指针。某一条链耗尽后，将另一条链的剩余部分整体接上。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = list1 != null ? list1 : list2;
return dummy.next;
}
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for list1 != nil && list2 != nil {
if list1.Val <= list2.Val {
tail.Next = list1
list1 = list1.Next
} else {
tail.Next = list2
list2 = list2.Next
}
tail = tail.Next
}
if list1 != nil {
tail.Next = list1
} else {
tail.Next = list2
}
return dummy.Next
}
23. 合并 K 个升序链表
把 k 条有序链表递归分为两组，分别合并，再复用两个有序链表的合并过程。空列表和只有一条链表时直接返回，分治使每轮合并规模均衡。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int lo, int hi) {
if (lo == hi) {
return lists[lo];
}
int mid = lo + (hi - lo) / 2;
return mergeTwoLists(merge(lists, lo, mid), merge(lists, mid + 1, hi));
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1 {
return lists[0]
}
mid := len(lists) / 2
l1 := mergeKLists(lists[:mid])
l2 := mergeKLists(lists[mid:])
return mergeTwoLists(l1, l2)
}
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
// 剩余的一条整段接上即可。
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
return dummy.Next
}
147. 对链表进行插入排序
维护一条已经有序的结果链，依次取出原链节点，在有序部分找到插入位置后接入。插入会改变当前节点的后继，所以必须先保存原链的下一个节点。
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode();
ListNode cur = head;
while (cur != null) {
// 先存后继，插入会改掉它。
ListNode next = cur.next;
ListNode pre = dummy;
while (pre.next != null && pre.next.val < cur.val) {
pre = pre.next;
}
cur.next = pre.next;
pre.next = cur;
cur = next;
}
return dummy.next;
}
}
func insertionSortList(head *ListNode) *ListNode {
dummy := &ListNode{}
cur := head
for cur != nil {
// 先存后继，插入会改掉它。
next := cur.Next
pre := dummy
for pre.Next != nil && pre.Next.Val < cur.Val {
pre = pre.Next
}
cur.Next = pre.Next
pre.Next = cur
cur = next
}
return dummy.Next
}
148. 排序链表
使用归并排序：快慢指针定位切分位置，断开左右两半，递归排序后合并。必须保证两个节点时能拆成一加一，且递归前确实断链，才能避免重复处理同一段。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 从 dummy 出发找中点，保证两节点时拆成 1 + 1。
ListNode dummy = new ListNode(0, head);
ListNode slow = dummy;
ListNode fast = dummy;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
slow.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(rightHead);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 从 dummy 出发找中点，保证两节点时拆成 1 + 1。
dummy := &ListNode{Next: head}
slow, fast := dummy, dummy
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
rightHead := slow.Next
slow.Next = nil
l1 := sortList(head)
l2 := sortList(rightHead)
return mergeSorted(l1, l2)
}
func mergeSorted(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
return dummy.Next
}
补充题 1. 排序奇升偶降链表
利用奇数位置递增、偶数位置递减的条件，先按位置拆成两条链并断尾，再反转偶数链，使两条链都递增。最后按合并两个有序链表的方式重新连接。
class Solution {
public ListNode sortOddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 拆成奇偶两条链。
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
// 断尾，防止成环。
odd.next = null;
// 反转偶数链，使其升序。
ListNode pre = null;
ListNode cur = evenHead;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 合并两个有序链表。
ListNode dummy = new ListNode();
ListNode tail = dummy;
ListNode l1 = head;
ListNode l2 = pre;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func sortOddEvenList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 拆成奇偶两条链。
odd, even := head, head.Next
evenHead := even
for even != nil && even.Next != nil {
odd.Next = odd.Next.Next
odd = odd.Next
even.Next = even.Next.Next
even = even.Next
}
// 断尾，防止成环。
odd.Next = nil
// 反转偶数链，使其升序。
var pre *ListNode
cur := evenHead
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 合并两个有序链表。
dummy := &ListNode{}
tail := dummy
l1, l2 := head, pre
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
tail.Next = l1
l1 = l1.Next
} else {
tail.Next = l2
l2 = l2.Next
}
tail = tail.Next
}
if l1 != nil {
tail.Next = l1
} else {
tail.Next = l2
}
return dummy.Next
}
七、加法与进位
2. 两数相加
数字按低位在前存储，可以从两个头节点直接逐位相加。每轮加上进位，取个位创建节点，将十位留给下一轮；两条链都结束后仍有进位时，需要补一个节点。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = sum / 10;
}
return dummy.next;
}
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
carry := 0
for l1 != nil || l2 != nil || carry != 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
tail.Next = &ListNode{Val: sum % 10}
tail = tail.Next
carry = sum / 10
}
return dummy.Next
}
445. 两数相加 II
数字按高位在前存储，先把两条链的数字分别压栈，以便从低位开始相加。结果节点使用头插法恢复高位在前的顺序，同时处理链长不同和最后一次进位。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new ArrayDeque<>();
Deque<Integer> stack2 = new ArrayDeque<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int sum = carry;
if (!stack1.isEmpty()) {
sum += stack1.pop();
}
if (!stack2.isEmpty()) {
sum += stack2.pop();
}
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
stack1 := make([]int, 0)
stack2 := make([]int, 0)
for l1 != nil {
stack1 = append(stack1, l1.Val)
l1 = l1.Next
}
for l2 != nil {
stack2 = append(stack2, l2.Val)
l2 = l2.Next
}
carry := 0
var head *ListNode
for len(stack1) > 0 || len(stack2) > 0 || carry != 0 {
sum := carry
if len(stack1) > 0 {
sum += stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
}
if len(stack2) > 0 {
sum += stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
}
node := &ListNode{Val: sum % 10, Next: head}
head = node
carry = sum / 10
}
return head
}
369. 给单链表加一
数字高位在前，先入栈再从低位开始处理，初始进位设为 1。每次取出一位与进位相加，用头插法构造结果；全为 9 时，需要在最高位补出 1。
class Solution {
public ListNode plusOne(ListNode head) {
Deque<Integer> stack = new ArrayDeque<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
stack.push(cur.val);
}
int carry = 1;
ListNode newHead = null;
while (!stack.isEmpty() || carry > 0) {
int sum = carry + (stack.isEmpty() ? 0 : stack.pop());
carry = sum / 10;
// 头插法：低位先建，挂在结果链前面。
newHead = new ListNode(sum % 10, newHead);
}
return newHead;
}
}
func plusOne(head *ListNode) *ListNode {
var stack []int
for cur := head; cur != nil; cur = cur.Next {
stack = append(stack, cur.Val)
}
carry := 1
var newHead *ListNode
for len(stack) > 0 || carry > 0 {
sum := carry
if len(stack) > 0 {
sum += stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
carry = sum / 10
// 头插法：低位先建，挂在结果链前面。
newHead = &ListNode{Val: sum % 10, Next: newHead}
}
return newHead
}
八、复制与展开
138. 随机链表的复制
采用原链与拷贝节点交织的方法：先在每个原节点后插入拷贝节点，再利用原 random 目标的后继设置拷贝 random，最后拆出新链并恢复原链。空 random 必须单独判断。
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 第一步：每个原节点后插入拷贝节点。
for (Node cur = head; cur != null; cur = cur.next.next) {
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
// 第二步：拷贝节点的 random 是原 random 的下一个节点。
for (Node cur = head; cur != null; cur = cur.next.next) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
}
// 第三步：拆分两条链，原链要复原。
Node newHead = head.next;
for (Node cur = head; cur != null; cur = cur.next) {
Node copy = cur.next;
cur.next = copy.next;
copy.next = (copy.next != null) ? copy.next.next : null;
}
return newHead;
}
}
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
// 第一步：每个原节点后插入拷贝节点。
for cur := head; cur != nil; cur = cur.Next.Next {
copy := &Node{Val: cur.Val, Next: cur.Next}
cur.Next = copy
}
// 第二步：拷贝节点的 random 是原 random 的下一个节点。
for cur := head; cur != nil; cur = cur.Next.Next {
if cur.Random != nil {
cur.Next.Random = cur.Random.Next
}
}
// 第三步：拆分两条链，原链要复原。
newHead := head.Next
for cur := head; cur != nil; cur = cur.Next {
copy := cur.Next
cur.Next = copy.Next
if copy.Next != nil {
copy.Next = copy.Next.Next
}
}
return newHead
}
430. 扁平化多级双向链表
按深度优先顺序展开多级链表。遇到 child 时先把原 next 压栈，再接入子链；走到当前链尾后弹栈接回未处理部分。连接时维护双向指针，并把已展开的 child 置空。
// 继续向前走，若链表走到尽头，则从栈中弹出之前保存的 next 接回。
class Solution {
public Node flatten(Node head) {
if (head == null) {
return null;
}
Deque<Node> stack = new ArrayDeque<>();
Node cur = head;
while (cur != null) {
if (cur.child != null) {
if (cur.next != null) {
stack.push(cur.next);
}
Node child = cur.child;
cur.next = child;
child.prev = cur;
cur.child = null;
} else if (cur.next == null && !stack.isEmpty()) {
Node next = stack.pop();
cur.next = next;
next.prev = cur;
}
cur = cur.next;
}
return head;
}
}
// 继续向前走，若链表走到尽头，则从栈中弹出之前保存的 next 接回。
func flatten(root *Node) *Node {
if root == nil {
return nil
}
stack := make([]*Node, 0)
cur := root
for cur != nil {
if cur.Child != nil {
if cur.Next != nil {
stack = append(stack, cur.Next)
}
child := cur.Child
cur.Next = child
child.Prev = cur
cur.Child = nil
} else if cur.Next == nil && len(stack) > 0 {
next := stack[len(stack)-1]
stack = stack[:len(stack)-1]
cur.Next = next
next.Prev = cur
}
cur = cur.Next
}
return root
}
九、前缀和与单调栈
1171. 从链表中删去总和值为零的连续节点
从虚拟头节点开始计算前缀和：两个位置的前缀和相同，说明中间一段和为零。第一遍记录每个前缀和最后出现的节点，第二遍直接跳到该节点的后继，一次删除对应零和区间。
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0, head);
Map<Integer, ListNode> lastSeen = new HashMap<>();
int prefixSum = 0;
for (ListNode cur = dummy; cur != null; cur = cur.next) {
prefixSum += cur.val;
// 记录前缀和最后出现的节点。
lastSeen.put(prefixSum, cur);
}
prefixSum = 0;
for (ListNode cur = dummy; cur != null; cur = cur.next) {
prefixSum += cur.val;
cur.next = lastSeen.get(prefixSum).next;
}
return dummy.next;
}
}
func removeZeroSumSublists(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
lastSeen := make(map[int]*ListNode)
prefixSum := 0
for cur := dummy; cur != nil; cur = cur.Next {
prefixSum += cur.Val
// 记录前缀和最后出现的节点。
lastSeen[prefixSum] = cur
}
prefixSum = 0
for cur := dummy; cur != nil; cur = cur.Next {
prefixSum += cur.Val
cur.Next = lastSeen[prefixSum].Next
}
return dummy.Next
}
1019. 链表中的下一个更大节点
先把节点值转成数组，再用单调栈保存尚未找到答案的下标。当前值大于栈顶对应值时，它就是该位置右侧第一个更大值，持续出栈填写答案；最后仍在栈中的位置保持 0。
class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> nums = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
nums.add(cur.val);
}
int[] res = new int[nums.size()];
// 单调递减栈，存下标。
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.size(); i++) {
while (!stack.isEmpty() && nums.get(i) > nums.get(stack.peek())) {
res[stack.pop()] = nums.get(i);
}
stack.push(i);
}
return res;
}
}
func nextLargerNodes(head *ListNode) []int {
var nums []int
for cur := head; cur != nil; cur = cur.Next {
nums = append(nums, cur.Val)
}
res := make([]int, len(nums))
// 单调递减栈，存下标。
var stack []int
for i, num := range nums {
for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
res[stack[len(stack)-1]] = num
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return res
}
十、树与缓存
109. 有序链表转换二叉搜索树
有序链表的中点可以作为平衡二叉搜索树的根。用快慢指针找中点并从前驱断开左右链，再分别递归构造左右子树；只有一个节点时直接返回，避免继续递归同一条链。
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
ListNode mid = findMiddle(head);
TreeNode root = new TreeNode(mid.val);
if (head == mid) {
// 只剩一个节点，避免死递归。
return root;
}
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
private ListNode findMiddle(ListNode head) {
ListNode pre = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if (pre != null) {
// 从中点前切断。
pre.next = null;
}
return slow;
}
}
func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
mid := findMiddle(head)
root := &TreeNode{Val: mid.Val}
if head == mid {
// 只剩一个节点，避免死递归。
return root
}
root.Left = sortedListToBST(head)
root.Right = sortedListToBST(mid.Next)
return root
}
func findMiddle(head *ListNode) *ListNode {
var pre *ListNode
slow, fast := head, head
for fast != nil && fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
if pre != nil {
// 从中点前切断。
pre.Next = nil
}
return slow
}
1367. 二叉树中的链表
从二叉树的每个节点尝试作为匹配起点。匹配时当前值必须相等，再沿左子节点或右子节点继续匹配链表后继；一次匹配失败后，可以换树上的其他节点重新开始。
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (root == null) {
return false;
}
// 以 root 为起点匹配，或换到左右子树找新起点。
return dfs(root, head) || isSubPath(head, root.left) || isSubPath(head, root.right);
}
private boolean dfs(TreeNode node, ListNode cur) {
if (cur == null) {
return true;
}
if (node == null || node.val != cur.val) {
return false;
}
return dfs(node.left, cur.next) || dfs(node.right, cur.next);
}
}
func isSubPath(head *ListNode, root *TreeNode) bool {
if root == nil {
return false
}
var dfs func(node *TreeNode, cur *ListNode) bool
dfs = func(node *TreeNode, cur *ListNode) bool {
if cur == nil {
return true
}
if node == nil || node.Val != cur.Val {
return false
}
return dfs(node.Left, cur.Next) || dfs(node.Right, cur.Next)
}
// 以 root 为起点匹配，或换到左右子树找新起点。
return dfs(root, head) || isSubPath(head, root.Left) || isSubPath(head, root.Right)
}
146. LRU 缓存
哈希表负责按键定位节点，双向链表负责维护最近使用顺序。读取或更新后把节点移到头部，插入超出容量时删除尾部最久未使用节点，同时从哈希表移除；头尾哨兵统一边界操作。
class LRUCache {
private static class Node {
int key;
int value;
Node prev;
Node next;
Node() {}
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> cache = new HashMap<>();
// 头尾哨兵，免去判空。
private final Node head = new Node();
private final Node tail = new Node();
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
if (cache.size() > capacity) {
Node removed = removeTail();
cache.remove(removed.key);
}
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private Node removeTail() {
Node node = tail.prev;
removeNode(node);
return node;
}
}
type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
capacity int
cache map[int]*Node
// 头尾哨兵，免去判空。
head, tail *Node
}
func Constructor(capacity int) LRUCache {
head, tail := &Node{}, &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make(map[int]*Node),
head: head,
tail: tail,
}
}
func (c *LRUCache) Get(key int) int {
node, ok := c.cache[key]
if !ok {
return -1
}
c.moveToHead(node)
return node.value
}
func (c *LRUCache) Put(key int, value int) {
if node, ok := c.cache[key]; ok {
node.value = value
c.moveToHead(node)
return
}
newNode := &Node{key: key, value: value}
c.cache[key] = newNode
c.addToHead(newNode)
if len(c.cache) > c.capacity {
removed := c.removeTail()
delete(c.cache, removed.key)
}
}
func (c *LRUCache) moveToHead(node *Node) {
c.removeNode(node)
c.addToHead(node)
}
func (c *LRUCache) addToHead(node *Node) {
node.prev = c.head
node.next = c.head.next
c.head.next.prev = node
c.head.next = node
}
func (c *LRUCache) removeNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (c *LRUCache) removeTail() *Node {
node := c.tail.prev
c.removeNode(node)
return node
}
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！