JavaGuide/docs/cs-basics/algorithms/linkedlist-algorithm-problems.md at main · duofuwang/JavaGuide

title

几道常见的链表算法题

description

精选链表高频题的思路与实现，覆盖两数相加、反转、环检测等场景，强调边界处理与复杂度分析。

1. 两数相加

题目描述

Leetcode:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

问题分析

Leetcode 官方详细解答地址：

https://leetcode-cn.com/problems/add-two-numbers/solution/

要对头结点进行操作时，考虑创建哑节点 dummy，使用 dummy->next 表示真正的头节点。这样可以避免处理头节点为空的边界问题。

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。

Solution

我们首先从最低有效位也就是列表 l1 和 l2 的表头开始相加。注意需要考虑到进位的情况！

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } *///https://leetcode-cn.com/problems/add-two-numbers/description/classSolution {
publicListNodeaddTwoNumbers(ListNodel1, ListNodel2) {
ListNodedummyHead = newListNode(0);
ListNodep = l1, q = l2, curr = dummyHead;
//carry 表示进位数intcarry = 0;
while (p != null || q != null) {
intx = (p != null) ? p.val : 0;
inty = (q != null) ? q.val : 0;
intsum = carry + x + y;
//进位数carry = sum / 10;
//新节点的数值为sum % 10curr.next = newListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = newListNode(carry);
}
returndummyHead.next;
}
}

2. 翻转链表

题目描述

剑指 offer:输入一个链表，反转链表后，输出链表的所有元素。

问题分析

这道算法题，说直白点就是：如何让后一个节点指向前一个节点！在下面的代码中定义了一个 next 节点，该节点主要是保存要反转到头的那个节点，防止链表 “断裂”。

Solution

publicclassListNode {
intval;
ListNodenext = null;
ListNode(intval) {
this.val = val;
}
}

/** * * @author Snailclimb * @date 2018年9月19日 * @Description: 反转单链表 */publicclassSolution {
publicListNodeReverseList(ListNodehead) {
ListNodenext = null;
ListNodepre = null;
while (head != null) {
// 保存要反转到头的那个节点next = head.next;
// 要反转的那个节点指向已经反转的上一个节点(备注:第一次反转的时候会指向null)head.next = pre;
// 上一个已经反转到头部的节点pre = head;
// 一直向链表尾走head = next;
}
returnpre;
}
}

测试方法：

publicstaticvoidmain(String[] args) {
ListNodea = newListNode(1);
ListNodeb = newListNode(2);
ListNodec = newListNode(3);
ListNoded = newListNode(4);
ListNodee = newListNode(5);
a.next = b;
b.next = c;
c.next = d;
d.next = e;
newSolution().ReverseList(a);
while (e != null) {
System.out.println(e.val);
e = e.next;
}
}

输出：

3. 链表中倒数第 k 个节点

题目描述

剑指 offer: 输入一个链表，输出该链表中倒数第 k 个结点。

问题分析

链表中倒数第 k 个节点也就是正数第（L-K+1）个节点，知道了这一点，这一题基本就没问题！

首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第 k 个节点也就是正数第（L-K+1）个节点。

Solution

/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/// 时间复杂度O(n),一次遍历即可// https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-rankingpublicclassSolution {
publicListNodeFindKthToTail(ListNodehead, intk) {
// 如果链表为空或者k小于等于0if (head == null || k <= 0) {
returnnull;
}
// 声明两个指向头结点的节点ListNodenode1 = head, node2 = head;
// 记录节点的个数intcount = 0;
// 记录k值，后面要使用intindex = k;
// p指针先跑，并且记录节点数，当node1节点跑了k-1个节点后，node2节点开始跑，// 当node1节点跑到最后时，node2节点所指的节点就是倒数第k个节点while (node1 != null) {
node1 = node1.next;
count++;
if (k < 1) {
node2 = node2.next;
}
k--;
}
// 如果节点个数小于所求的倒数第k个节点，则返回空if (count < index)
returnnull;
returnnode2;
}
}

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

Leetcode:给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

该题在 LeetCode 上有详细解答，具体可参考 LeetCode。

问题分析

我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第（L - n + 1）个结点，其中 L 是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。

Solution

两次遍历法

首先我们将添加一个 哑结点 作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第（L - n）个结点那里。我们把第（L - n）个结点的 next 指针重新链接至第（L - n + 2）个结点，完成这个算法。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/publicclassSolution {
publicListNoderemoveNthFromEnd(ListNodehead, intn) {
// 哑结点，哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部ListNodedummy = newListNode(0);
// 哑结点指向头结点dummy.next = head;
// 保存链表长度intlength = 0;
ListNodelen = head;
while (len != null) {
length++;
len = len.next;
}
length = length - n;
ListNodetarget = dummy;
// 找到 L-n 位置的节点while (length > 0) {
target = target.next;
length--;
}
// 把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点target.next = target.next.next;
returndummy.next;
}
}

进阶——一次遍历法：

链表中倒数第 N 个节点也就是正数第（L - n + 1）个节点。

其实这种方法就和我们上面第四题找“链表中倒数第 k 个节点”所用的思想是一样的。基本思路就是： 定义两个节点 node1、node2；node1 节点先跑，node1 节点跑到第 n+1 个节点的时候，node2 节点开始跑。当 node1 节点跑到最后一个节点时，node2 节点所在的位置就是第（L - n）个节点（L 代表总链表长度，也就是倒数第 n + 1 个节点）。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */publicclassSolution {
publicListNoderemoveNthFromEnd(ListNodehead, intn) {
ListNodedummy = newListNode(0);
dummy.next = head;
// 声明两个指向头结点的节点ListNodenode1 = dummy, node2 = dummy;
// node1 节点先跑，node1节点 跑到第 n 个节点的时候,node2 节点开始跑// 当node1 节点跑到最后一个节点时，node2 节点所在的位置就是第 （L-n ） 个节点，也就是倒数第 n+1（L代表总链表长度）while (node1 != null) {
node1 = node1.next;
if (n < 1 && node1 != null) {
node2 = node2.next;
}
n--;
}
node2.next = node2.next.next;
returndummy.next;
}
}

5. 合并两个排序的链表

题目描述

剑指 offer:输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

问题分析

我们可以这样分析：

假设我们有两个链表 A，B；
A 的头节点 A1 的值与 B 的头结点 B1 的值比较，假设 A1 小，则 A1 为头节点；
A2 再和 B1 比较，假设 B1 小，则 A1 指向 B1；
A2 再和 B2 比较
就这样循环往复就行了，应该还算好理解。

考虑通过递归的方式实现！

Solution

递归版本：

/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*///https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-rankingpublicclassSolution {
publicListNodeMerge(ListNodelist1, ListNodelist2) {
if (list1 == null) {
returnlist2;
}
if (list2 == null) {
returnlist1;
}
if (list1.val <= list2.val) {
list1.next = Merge(list1.next, list2);
returnlist1;
} else {
list2.next = Merge(list1, list2.next);
returnlist2;
}
}
}

面试复盘重点

链表题的代码通常不长，但指针更新顺序很容易写错。面试前至少要掌握 4 个模板：虚拟头节点、反转链表、快慢指针、合并链表。

模板	适用题型	关键点
虚拟头节点	删除节点、合并链表、头节点可能变化	返回 `dummy.next`
反转链表	整体反转、区间反转、K 个一组反转	保存 `next`，再改 `cur.next`
快慢指针	环检测、倒数第 K 个、中点	先判断 `fast` 和 `fast.next`
合并链表	两个有序链表、K 个有序链表	递归或迭代，注意尾部接上剩余链表

反转链表的迭代模板建议背熟：

ListNodereverseList(ListNodehead) {
ListNodeprev = null;
ListNodecur = head;
while (cur != null) {
ListNodenext = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
returnprev;
}

过程示意和边界样例

反转链表时，核心是先保存 next，再修改 cur.next。可以按下面的指针变化来记：

初始：prev = null, cur = head
每一轮：
next = cur.next
cur.next = prev
prev = cur
cur = next
结束：cur == null，prev 指向新头节点

删除节点、合并链表这类题，优先考虑虚拟头节点：

ListNodedummy = newListNode(0);
dummy.next = head;
// 中间统一操作 dummy 后面的链表returndummy.next;

几个易错点：

删除倒数第 N 个节点时，虚拟头节点能统一处理删除头节点的情况。
区间反转要先保存区间前一个节点和区间后一个节点。
判断链表有环时，循环条件是 fast != null && fast.next != null。
递归合并链表代码短，但链表很长时可能有递归栈风险。
空链表、单节点链表、删除头节点、删除尾节点都要单独过一遍。

FilesExpand file tree

linkedlist-algorithm-problems.md

Latest commit

History

linkedlist-algorithm-problems.md

File metadata and controls

1. 两数相加

题目描述

问题分析

Solution

2. 翻转链表

题目描述

问题分析

Solution

3. 链表中倒数第 k 个节点

题目描述

问题分析

Solution

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

问题分析

Solution

5. 合并两个排序的链表

题目描述

问题分析

Solution

面试复盘重点

过程示意和边界样例