Appearance
高频链表
两两交换链表节点
两两交换链表节点
题意：给你一个链表，把相邻两个节点交换位置。注意是交换节点本身，不是只交换节点里的值。
核心用 dummy 虚拟头节点。每次看 prev 后面的两个节点：
first = prev.nextsecond = first.nextnext = second.next
然后重新连接成：
c
prev -> second -> first -> next
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.next = next; // 初始化当前节点的 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode SwapPairs(ListNode head) // 定义两两交换链表节点的方法
{ // 方法开始
ListNode dummy = new ListNode(0); // 创建虚拟头节点，方便处理头节点被交换的情况
dummy.next = head; // 让 dummy 指向原链表头节点
ListNode prev = dummy; // prev 指向每一组两个节点的前一个节点
while (prev.next != null && prev.next.next != null) // 只要 prev 后面至少还有两个节点，就可以交换
{ // 循环开始
ListNode first = prev.next; // first 指向这一组的第一个节点
ListNode second = first.next; // second 指向这一组的第二个节点
ListNode next = second.next; // next 保存第二个节点后面的节点，防止链表断掉
first.next = next; // 第一个节点交换后要接到后面的 next
second.next = first; // 第二个节点交换后要接到第一个节点前面
prev.next = second; // prev 要接到交换后的新头节点 second
prev = first; // prev 移动到交换后的这一组尾部，准备处理下一组
} // 循环结束
return dummy.next; // 返回新的链表头节点
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，每个节点只处理一次。 空间复杂度：O(1)，只用了几个指针变量。
面试记忆
NOTE
dummy 接头，prev 找一对；first 接 next，second 接 first，prev 接 second，最后 prev 移到 first。
K 个一组翻转链表
K 个一组翻转链表
题意：链表每 k 个节点翻转一次；如果最后剩下的节点不足 k 个，就保持原样。
核心：每一组先确认够不够 k 个。够，就反转这一段；不够，直接结束。
c
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化当前节点的值
this.next = next; // 初始化当前节点的 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode ReverseKGroup(ListNode head, int k) // 定义 K 个一组翻转链表的方法
{ // 方法开始
if (head == null || k <= 1) // 如果链表为空，或者 k 为 1
{ // 条件开始
return head; // 不需要翻转，直接返回原链表
} // 条件结束
ListNode dummy = new ListNode(0, head); // 创建虚拟头节点，方便处理第一组被翻转的情况
ListNode groupPrev = dummy; // groupPrev 指向当前组的前一个节点
while (true) // 不断尝试处理下一组
{ // 循环开始
ListNode kth = GetKth(groupPrev, k); // 从 groupPrev 往后找第 k 个节点
if (kth == null) // 如果找不到第 k 个节点
{ // 条件开始
break; // 说明剩余节点不足 k 个，停止翻转
} // 条件结束
ListNode groupNext = kth.next; // 保存当前组后面的第一个节点
ListNode prev = groupNext; // 反转时 prev 先指向 groupNext，用来接回后半段
ListNode curr = groupPrev.next; // curr 指向当前组的第一个节点
while (curr != groupNext) // 只反转当前这一组，直到走到 groupNext 停止
{ // 反转循环开始
ListNode temp = curr.next; // 暂存 curr 的下一个节点，防止断链
curr.next = prev; // 当前节点指向前一个节点
prev = curr; // prev 前进到当前节点
curr = temp; // curr 前进到原来的下一个节点
} // 反转循环结束
ListNode oldGroupHead = groupPrev.next; // 记录翻转前的组头，翻转后它会变成组尾
groupPrev.next = kth; // 当前组前面的节点接到翻转后的新组头 kth
groupPrev = oldGroupHead; // groupPrev 移到当前组尾部，准备处理下一组
} // 循环结束
return dummy.next; // 返回新的链表头节点
} // 方法结束
private ListNode GetKth(ListNode start, int k) // 从 start 往后走 k 步，找到当前组的第 k 个节点
{ // 方法开始
while (start != null && k > 0) // 只要节点没空，并且还没走够 k 步
{ // 循环开始
start = start.next; // 指针向后移动一步
k--; // 剩余步数减 1
} // 循环结束
return start; // 返回找到的第 k 个节点，找不到则返回 null
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，每个节点只被处理常数次。 空间复杂度：O(1)，只用了几个指针变量。
面试记忆
TIP
先找够 k 个；保存 groupNext；把这一段反转到 groupNext 前面；最后 groupPrev 移到旧组头。
删除链表倒数第 N 个节点
删除链表倒数第 N 个节点
题意：删除链表中倒数第 N 个节点，并返回新的头节点。
核心用快慢指针：
先让 fast 走 n 步。 然后 fast 和 slow 一起走。 当 fast 到最后一个节点时，slow.next 正好是要删除的节点。
c
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化节点的值
this.next = next; // 初始化节点的 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode RemoveNthFromEnd(ListNode head, int n) // 删除链表倒数第 n 个节点
{ // 方法开始
ListNode dummy = new ListNode(0, head); // 创建虚拟头节点，方便删除真正的头节点
ListNode fast = dummy; // fast 指针从 dummy 开始
ListNode slow = dummy; // slow 指针也从 dummy 开始
for (int i = 0; i < n; i++) // 让 fast 先向前走 n 步
{ // 循环开始
fast = fast.next; // fast 向后移动一个节点
} // 循环结束
while (fast.next != null) // 当 fast 还没有到最后一个节点时
{ // 循环开始
fast = fast.next; // fast 向后移动
slow = slow.next; // slow 同步向后移动
} // 循环结束
slow.next = slow.next.next; // 删除 slow 后面的节点，也就是倒数第 n 个节点
return dummy.next; // 返回新的头节点
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，只遍历一次链表。 空间复杂度：O(1)，只用了几个指针。
面试记忆
IMPORTANT
dummy 接头；fast 先走 N 步；fast 到尾时 slow 在目标前面；跳过 slow.next。
合并 K 个升序链表
合并 K 个升序链表
题意：给你 K 个已经升序的链表，把它们合并成一个新的升序链表。
核心用小根堆：堆里始终放每条链表当前的头节点。每次弹出最小节点，接到结果链表后，再把这个节点的 next 放回堆里。
c
using System.Collections.Generic; // 引入 PriorityQueue 和集合类型
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化节点值
this.next = next; // 初始化 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode MergeKLists(ListNode[] lists) // 定义合并 K 个升序链表的方法
{ // 方法开始
PriorityQueue<ListNode, int> heap = new PriorityQueue<ListNode, int>(); // 创建小根堆，优先级使用节点值
foreach (ListNode node in lists) // 遍历每一条链表的头节点
{ // 循环开始
if (node != null) // 如果当前链表不是空链表
{ // 条件开始
heap.Enqueue(node, node.val); // 把当前链表头节点放入小根堆
} // 条件结束
} // 循环结束
ListNode dummy = new ListNode(0); // 创建虚拟头节点，方便拼接结果链表
ListNode tail = dummy; // tail 指向结果链表的尾部
while (heap.Count > 0) // 只要堆里还有候选节点
{ // 循环开始
ListNode node = heap.Dequeue(); // 弹出当前最小的节点
tail.next = node; // 把最小节点接到结果链表尾部
tail = tail.next; // tail 移动到新的尾节点
if (node.next != null) // 如果被弹出的节点后面还有节点
{ // 条件开始
heap.Enqueue(node.next, node.next.val); // 把后继节点加入堆，成为新的候选节点
} // 条件结束
} // 循环结束
tail.next = null; // 断开尾节点后面的旧连接，保证结果链表结尾干净
return dummy.next; // 返回真正的结果链表头节点
} // 方法结束
} // 题解类结束复杂度
设所有链表节点总数是 N，链表数量是 K。 时间复杂度：O(N log K)。 空间复杂度：O(K)，堆里最多放 K 个节点。
面试记忆
WARNING
先把所有非空头节点入堆；每次弹出最小节点接到 tail；如果它有 next，就把 next 入堆。
链表排序
链表排序
链表排序面试里最推荐讲归并排序。因为链表不适合随机访问，快排那种按下标交换的思路不舒服；但链表很适合“切开 + 合并”。
核心步骤：
快慢指针找到中点。 把链表切成左右两段。 递归排序左右链表。 合并两个有序链表。
c
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化节点值
this.next = next; // 初始化 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode SortList(ListNode head) // 定义链表排序方法
{ // 方法开始
if (head == null || head.next == null) // 如果链表为空或者只有一个节点
{ // 条件开始
return head; // 本身已经有序，直接返回
} // 条件结束
ListNode slow = head; // slow 每次走一步，用来找中点
ListNode fast = head.next; // fast 每次走两步，让 slow 停在左半段尾部
while (fast != null && fast.next != null) // 当 fast 还能继续走两步时
{ // 循环开始
slow = slow.next; // slow 向后走一步
fast = fast.next.next; // fast 向后走两步
} // 循环结束
ListNode rightHead = slow.next; // 右半段的头节点
slow.next = null; // 切断左右两段链表
ListNode left = SortList(head); // 递归排序左半段
ListNode right = SortList(rightHead); // 递归排序右半段
return Merge(left, right); // 合并两个已经有序的链表并返回
} // 方法结束
private ListNode Merge(ListNode left, ListNode right) // 合并两个升序链表
{ // 方法开始
ListNode dummy = new ListNode(0); // 创建虚拟头节点，方便拼接结果
ListNode tail = dummy; // tail 指向结果链表的尾部
while (left != null && right != null) // 当两个链表都还有节点时
{ // 循环开始
if (left.val <= right.val) // 如果左链表当前节点更小或相等
{ // 条件开始
tail.next = left; // 把左链表当前节点接到结果链表后面
left = left.next; // 左链表指针向后移动
} // 条件结束
else // 如果右链表当前节点更小
{ // 分支开始
tail.next = right; // 把右链表当前节点接到结果链表后面
right = right.next; // 右链表指针向后移动
} // 分支结束
tail = tail.next; // 结果链表尾指针向后移动
} // 循环结束
tail.next = left != null ? left : right; // 把剩余没有合并完的链表直接接上
return dummy.next; // 返回真正的排序后头节点
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n log n)。 空间复杂度：递归写法是 O(log n)，主要是递归栈。 如果写自底向上的归并，可以做到 O(1) 额外空间。
面试记忆
CAUTION
快慢指针找中点，断开左右两段；递归排好两边，再按“合并两个有序链表”的方式合并。
相交链表
相交链表
题意：判断两个单链表是否在某个节点相交。注意，相交不是值相等，而是两个链表后面共享同一个节点对象。
核心用双指针换头走：
pA 从 headA 出发，走完 A 后去走 B。 pB 从 headB 出发，走完 B 后去走 A。 如果两个链表相交，它们最终会在交点相遇。 如果不相交，它们最终会一起变成 null。
c
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int x) // 定义节点构造函数
{ // 构造函数开始
val = x; // 初始化节点值
next = null; // 初始化 next 指针为空
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) // 查找两个链表的相交节点
{ // 方法开始
if (headA == null || headB == null) // 如果任意一个链表为空
{ // 条件开始
return null; // 一定不可能相交，直接返回 null
} // 条件结束
ListNode pA = headA; // pA 从链表 A 的头节点出发
ListNode pB = headB; // pB 从链表 B 的头节点出发
while (pA != pB) // 只要两个指针没有指向同一个节点，就继续移动
{ // 循环开始
pA = pA == null ? headB : pA.next; // pA 走完 A 后切换到 B 的头节点
pB = pB == null ? headA : pB.next; // pB 走完 B 后切换到 A 的头节点
} // 循环结束
return pA; // 返回相交节点；如果不相交，此时 pA 和 pB 都是 null
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(m + n)。 空间复杂度：O(1)。
面试记忆
NOTE
pA 到尾去 headB，pB 到尾去 headA；相交就在交点相遇，不相交就在 null 相遇。
复制带随机指针的链表
复制带随机指针的链表
题意：链表节点除了 next，还有一个 random 指针，它可能指向任意节点，也可能是 null。要求复制出一条全新的链表，新链表的 next 和 random 都不能指回原链表节点。
核心用三步穿插复制法：
第一步：每个原节点后面插入它的复制节点。 第二步：复制 random，关键公式是 copy.random = current.random.next。 第三步：把穿插链表拆成原链表和复制链表。
c
public class Node // 定义带 random 指针的链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public Node next; // 指向下一个节点的指针
public Node random; // 指向任意节点的随机指针
public Node(int val) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化节点值
this.next = null; // 初始化 next 指针为空
this.random = null; // 初始化 random 指针为空
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public Node CopyRandomList(Node head) // 定义复制带随机指针链表的方法
{ // 方法开始
if (head == null) // 如果原链表为空
{ // 条件开始
return null; // 空链表复制后仍然是空
} // 条件结束
Node current = head; // current 用来遍历原链表
while (current != null) // 第一步：在每个原节点后面插入复制节点
{ // 循环开始
Node copy = new Node(current.val); // 创建当前节点的复制节点
copy.next = current.next; // 复制节点先接到原节点的下一个节点
current.next = copy; // 原节点接到复制节点
current = copy.next; // current 跳到下一个原节点
} // 循环结束
current = head; // current 重新回到原链表头节点
while (current != null) // 第二步：复制 random 指针
{ // 循环开始
Node copy = current.next; // 当前原节点后面的节点就是它的复制节点
if (current.random != null) // 如果当前原节点有 random 指针
{ // 条件开始
copy.random = current.random.next; // 原 random 指向节点的 next，就是 random 目标的复制节点
} // 条件结束
current = copy.next; // current 跳到下一个原节点
} // 循环结束
current = head; // current 再次回到原链表头节点
Node copyHead = head.next; // 复制链表的头节点是原头节点后面的复制节点
while (current != null) // 第三步：拆分原链表和复制链表
{ // 循环开始
Node copy = current.next; // 当前原节点对应的复制节点
Node nextOriginal = copy.next; // 下一个原节点
current.next = nextOriginal; // 恢复原链表的 next 指针
copy.next = nextOriginal != null ? nextOriginal.next : null; // 复制节点接到下一个复制节点
current = nextOriginal; // current 移动到下一个原节点
} // 循环结束
return copyHead; // 返回复制链表的头节点
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，整条链表扫描三次。 额外空间复杂度：O(1)，不算必须创建的新节点。
面试记忆
IMPORTANT
原节点后面插副本；副本的 random 指向原 random 的 next；最后把奇偶位置拆成两条链表。
回文链表
回文链表
题意：判断一个链表是不是回文。比如：
1 -> 2 -> 2 -> 1 是回文。 1 -> 2 -> 3 不是回文。
核心做法： 快慢指针找到中点，反转后半段，然后前半段和后半段逐个比较。
c
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化节点值
this.next = next; // 初始化 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public bool IsPalindrome(ListNode head) // 判断链表是否是回文链表
{ // 方法开始
if (head == null || head.next == null) // 如果链表为空或者只有一个节点
{ // 条件开始
return true; // 空链表和单节点链表都可以认为是回文
} // 条件结束
ListNode slow = head; // slow 每次走一步，用来找前半段尾部
ListNode fast = head; // fast 每次走两步，用来帮助 slow 定位中点
while (fast.next != null && fast.next.next != null) // 当 fast 还能继续走两步时
{ // 循环开始
slow = slow.next; // slow 向后走一步
fast = fast.next.next; // fast 向后走两步
} // 循环结束
ListNode secondHalfHead = ReverseList(slow.next); // 反转后半段链表
ListNode left = head; // left 从前半段头节点开始
ListNode right = secondHalfHead; // right 从反转后的后半段头节点开始
bool result = true; // 默认认为链表是回文
while (right != null) // 只需要比较后半段长度
{ // 循环开始
if (left.val != right.val) // 如果前后对应节点的值不相等
{ // 条件开始
result = false; // 标记不是回文链表
break; // 已经确定不是回文，可以停止比较
} // 条件结束
left = left.next; // left 向后移动
right = right.next; // right 向后移动
} // 循环结束
slow.next = ReverseList(secondHalfHead); // 把后半段再反转回来，恢复原链表结构
return result; // 返回最终判断结果
} // 方法结束
private ListNode ReverseList(ListNode head) // 反转单链表
{ // 方法开始
ListNode prev = null; // prev 表示已经反转部分的头节点
ListNode curr = head; // curr 表示当前正在处理的节点
while (curr != null) // 只要当前节点不为空，就继续反转
{ // 循环开始
ListNode next = curr.next; // 保存 curr 的下一个节点，防止断链
curr.next = prev; // 当前节点指向前一个节点
prev = curr; // prev 移动到当前节点
curr = next; // curr 移动到原来的下一个节点
} // 循环结束
return prev; // prev 就是反转后的新头节点
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)。 空间复杂度：O(1)。
面试记忆
NOTE
快慢指针找中点，反转后半段，前后两段同步比较；最后可以把后半段恢复回来，显得更严谨。
奇偶链表
奇偶链表
题意：把链表中奇数位置的节点放前面，偶数位置的节点放后面，并保持各自原来的相对顺序。
注意：这里的奇偶指的是节点位置，不是节点值。 1 -> 2 -> 3 -> 4 -> 5 变成 1 -> 3 -> 5 -> 2 -> 4。
核心：维护两条链。
odd 负责串起奇数位置节点。 even 负责串起偶数位置节点。 evenHead 保存偶数链表头，最后接到奇数链表尾部。
c
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化节点值
this.next = next; // 初始化 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode OddEvenList(ListNode head) // 定义奇偶链表重排方法
{ // 方法开始
if (head == null || head.next == null) // 如果链表为空或者只有一个节点
{ // 条件开始
return head; // 不需要重排，直接返回
} // 条件结束
ListNode odd = head; // odd 指向当前奇数位置链表的尾节点
ListNode even = head.next; // even 指向当前偶数位置链表的尾节点
ListNode evenHead = even; // 保存偶数位置链表的头节点，最后要接回去
while (even != null && even.next != null) // 只要后面还有下一个奇数位置节点
{ // 循环开始
odd.next = even.next; // 奇数链表接上下一个奇数位置节点
odd = odd.next; // odd 移动到新的奇数链表尾节点
even.next = odd.next; // 偶数链表接上下一个偶数位置节点
even = even.next; // even 移动到新的偶数链表尾节点
} // 循环结束
odd.next = evenHead; // 奇数链表尾部接上偶数链表头部
return head; // 返回重排后的链表头节点
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)，每个节点只处理一次。 空间复杂度：O(1)，只用了几个指针。
面试记忆
IMPORTANT
odd 接下一个奇数位，even 接下一个偶数位；最后 odd 尾巴接 evenHead。
旋转链表
旋转链表
题意：把链表整体向右旋转 k 个位置。
比如：
1 -> 2 -> 3 -> 4 -> 5，k = 2 结果是：
4 -> 5 -> 1 -> 2 -> 3
核心：先把链表连成环，再在新的尾节点处断开。
c
public class ListNode // 定义单链表节点类
{ // 节点类开始
public int val; // 节点保存的值
public ListNode next; // 指向下一个节点的指针
public ListNode(int val = 0, ListNode next = null) // 定义节点构造函数
{ // 构造函数开始
this.val = val; // 初始化节点值
this.next = next; // 初始化 next 指针
} // 构造函数结束
} // 节点类结束
public class Solution // 定义题解类
{ // 题解类开始
public ListNode RotateRight(ListNode head, int k) // 定义向右旋转链表的方法
{ // 方法开始
if (head == null || head.next == null || k == 0) // 如果链表为空、只有一个节点，或者 k 为 0
{ // 条件开始
return head; // 不需要旋转，直接返回原链表
} // 条件结束
int length = 1; // 记录链表长度，初始包含头节点
ListNode tail = head; // tail 用来找到链表尾节点
while (tail.next != null) // 只要还没走到尾节点
{ // 循环开始
tail = tail.next; // tail 向后移动
length++; // 链表长度加 1
} // 循环结束
k = k % length; // k 可能大于链表长度，所以先取模
if (k == 0) // 如果取模后 k 为 0
{ // 条件开始
return head; // 说明旋转后和原链表一样
} // 条件结束
tail.next = head; // 尾节点接回头节点，把链表临时变成环
int stepsToNewTail = length - k - 1; // 新尾节点距离原头节点的步数
ListNode newTail = head; // newTail 从原头节点开始走
for (int i = 0; i < stepsToNewTail; i++) // 走到新的尾节点位置
{ // 循环开始
newTail = newTail.next; // newTail 向后移动一步
} // 循环结束
ListNode newHead = newTail.next; // 新尾节点的下一个节点就是新的头节点
newTail.next = null; // 从新尾节点处断开环，形成新的链表
return newHead; // 返回旋转后的新头节点
} // 方法结束
} // 题解类结束复杂度
时间复杂度：O(n)。 空间复杂度：O(1)。
面试记忆
CAUTION
先求长度和尾节点；k 取模；尾接头成环；走到新尾节点，断开它的 next。