【链表】一文搞定链表算法：从基础到实战

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

什么是链表算法：

链表算法，是围绕链表数据结构构建的一系列操作方法。链表由一个个节点组成，节点间靠指针相连，内存存储不连续。链表算法涵盖诸多方面，像创建链表，按特定逻辑将节点串联起来；插入节点，能灵活添加新数据；删除节点，可移除指定元素。遍历链表能逐个访问数据，查找则用于定位特定值。此外，还有链表反转、合并等复杂操作。在实际应用中，链表算法在操作系统任务调度、数据库索引管理等方面发挥关键作用，为高效处理动态数据提供有力支持 。

下面，本篇文章将通过以下几个例题详细介绍阐述链表算法相关知识！

例题

一、两数相加

1. 题目链接：两数相加
2. 题目描述：

给你两个 ⾮空 的链表，表⽰两个⾮负的整数。它们每位数字都是按照 逆序 的⽅式存储的，并且每个 节点只能存储 ⼀位 数字。 请你将两个数相加，并以相同形式返回⼀个表⽰和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
⽰例 3：
输⼊：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示： 每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零

3. 解法（模拟）：
   两个链表都是逆序存储数字的，即两个链表的个位数、⼗位数等都已经对应，可以直接相加。 在相加过程中，我们要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加。如果产⽣进位的位置在链表尾部，即答案位数⽐原链表位数⻓⼀位，还需要再 new ⼀个结点储存最⾼位。
4. 代码示例：

   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode newHead = new ListNode(0);ListNode prev = newHead;int t = 0;while (l1 != null || l2 != null || t != 0) {if (l1 != null) {t += l1.val;l1 = l1.next;}if (l2 != null) {t += l2.val;l2 = l2.next;}prev.next = new ListNode(t % 10);prev = prev.next;t /= 10;}return newHead.next;}

二、两两交换链表中的节点

1. 题目链接：两两交换链表中的节点
2. 题目描述：

给你⼀个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的 值的情况下完成本题（即，只能进行节点交换）。
示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
⽰例 2：
输⼊：head = []
输出：[]
⽰例 3：
输⼊：head = [1]
输出：[1]
提⽰：
链表中节点的数⽬在范围 [0, 100] 内 0 <= Node.val <= 100

3. 解法（模拟）：
   算法思路：通过画图模拟算法！

4. 代码示例：

  public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = new ListNode(0);newHead.next = head;ListNode prev = newHead, cur = prev.next, next = cur.next, nnext = next.next;while (cur != null && next != null) {prev.next = next;next.next = cur;cur.next = nnext;prev = cur;cur = nnext;if (cur != null) next = cur.next;if (next != null) nnext = next.next;}return newHead.next;}

这里，这道题仍有第二种解法：递归，本篇不重点讨论递归，仅将代码示例放于此文：

  public ListNode swapPairs(ListNode head) {if(head==null||head.next == null){return head;}ListNode newhead = swapPairs(head.next.next);ListNode ret = head.next;ret.next = head;head.next = newhead;return ret;}

三、重排链表

1. 题目链接：重排链表
2. 题目描述：

给定⼀个单链表 L 的头节点 head ，单链表 L 表⽰为：L(0) → L(1) → … → L(n - 1) → L(n)
请将其重新排列后变为：L(0) → L(n) → L(1) → L(n - 1) → L(2) → L(n - 2) → 不能只是单纯的改变节点内部的值，⽽是需要实际的进行节点交换。
⽰例 1：
输⼊：head = [1,2,3,4]
输出：[1,4,2,3]
⽰例 2：
输⼊：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
提示：
• 链表的长度范围为 [1, 5 * 10(4)]
• 1 <= node.val <= 1000

3. 解法：
   算法思路：
   找中间节点；
   中间部分往后的逆序；
   合并两个链表

4. 代码示例：

 public void reorderList(ListNode head) {if (head == null || head.next == null || head.next.next == null) return;ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode newHead = new ListNode(0);ListNode cur = slow.next;slow.next = null;//切断链表//头插while (cur != null) {ListNode next = cur.next;cur.next = newHead.next;newHead.next = cur;cur = next;}//合并ListNode cur1 = head, cur2 = newHead.next;ListNode ret = new ListNode(0);ListNode prev = ret;while (cur1 != null) {//先放第一个链表prev.next = cur1;prev = cur1;cur1 = cur1.next;//在合并第二个链表if (cur2 != null) {prev.next = cur2;prev = cur2;cur2 = cur2.next;}}}

四、合并K个升序链表

1. 题目链接：合并K个升序链表
2. 题目描述：

给你⼀个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到⼀个升序链表中，返回合并后的链表。
⽰例 1： 输⼊：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到⼀个有序链表中得到。
1->1->2->3->4->4->5->6
⽰例 2：
输⼊：lists = []
输出：[]
⽰例 3：
输⼊：lists = [[]]
输出：[]
提⽰： k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

3. 解法⼀（利用堆）：
   算法思路：
   合并两个有序链表是比较简单且做过的，就是⽤双指针依次比较链表 1 、链表 2 未排序的最⼩元 素，选择更小的那⼀个加⼊有序的答案链表中。 合并 K 个升序链表时，我们依旧可以选择 K 个链表中，头结点值最小的那⼀个。那么如何快速的得 到头结点最小的是哪⼀个呢？⽤堆这个数据结构就好啦~ 我们可以把所有的头结点放进⼀个⼩根堆中，这样就能快速的找到每次 K 个链表中，最小的元素是哪个。

4. 代码示例：

 public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);// 将所有的头节点加入到小根堆中for (ListNode l : lists) {if (l != null) {heap.offer(l);}}//合并ListNode ret = new ListNode(0);ListNode prev = ret;while (!heap.isEmpty()) {ListNode t = heap.poll();prev.next = t;prev = t;if (t.next != null) heap.offer(t.next);}return ret.next;}

五、 K个⼀组翻转链表

1. 题目链接：K个⼀组翻转链表
2. 题目描述：

给你链表的头节点 head ，每 k 个节点⼀组进行翻转，请你返回修改后的链表。
k 是⼀个正整数，它的值⼩于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余 的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，⽽是需要实际进⾏节点交换。
⽰例 1：

输⼊：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
⽰例 2：

输⼊：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
提⽰： 链表中的节点数⽬为 n 1 <= k <= n <= 5000
0 <= Node.val <= 1000

3. 解法（模拟）：
   算法思路：
   本题的⽬标⾮常清晰易懂，不涉及复杂的算法，只是实现过程中需要考虑的细节比较多。 我们可以把链表按 K 个为⼀组进⾏分组，组内进⾏反转，并且记录反转后的头尾结点，使其可以和 前、后连接起来。思路⽐较简单，但是实现起来是⽐较复杂的。
   我们可以先求出⼀共需要逆序多少组（假设逆序 n 组），然后重复 n 次⻓度为 k 的链表的逆序即 可。
4. 代码示例：

  public ListNode reverseKGroup(ListNode head, int k) {if (head == null || head.next == null) return head;int n = 0;ListNode cur = head;while (cur != null) {cur = cur.next;n++;}n /= k;ListNode newHead = new ListNode(0);ListNode prev = new ListNode(0);cur = head;for (int i = 0; i < n; i++) {ListNode tmp = cur;for (int j = 0; j < k; j++) {//头插逻辑ListNode next = cur.next;cur.next = prev.next;prev.next = cur;cur = next;}prev = tmp;}// 把后面不需要逆序的地方链接起来prev.next = cur;return newHead.next;}

结语

本文到这里就结束了，主要介绍了链表算法，并通过几道例题更加深入了解链表算法相关知识，重点在于画图理清题目思路，注重代码细节。希望能够对你有帮助！

以上就是本文全部内容，感谢各位能够看到最后，创作不易，希望大家多多支持！

最后，大家再见！祝好！我们下期见！