【链表】一文搞定链表算法：从基础到实战
提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 前言
- 例题
- 一、两数相加
- 二、两两交换链表中的节点
- 三、重排链表
- 四、合并K个升序链表
- 五、 K个⼀组翻转链表
- 结语
前言
什么是链表算法：
链表算法，是围绕链表数据结构构建的一系列操作方法。链表由一个个节点组成，节点间靠指针相连，内存存储不连续。链表算法涵盖诸多方面，像创建链表，按特定逻辑将节点串联起来；插入节点，能灵活添加新数据；删除节点，可移除指定元素。遍历链表能逐个访问数据，查找则用于定位特定值。此外，还有链表反转、合并等复杂操作。在实际应用中，链表算法在操作系统任务调度、数据库索引管理等方面发挥关键作用，为高效处理动态数据提供有力支持 。
下面，本篇文章将通过以下几个例题详细介绍阐述链表算法相关知识！
例题
一、两数相加
- 题目链接：两数相加
- 题目描述：
给你两个 ⾮空 的链表，表⽰两个⾮负的整数。它们每位数字都是按照 逆序 的⽅式存储的，并且每个 节点只能存储 ⼀位 数字。 请你将两个数相加，并以相同形式返回⼀个表⽰和的链表。 你可以假设除了数字 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 题目数据保证列表表示的数字不含前导零
- 解法（模拟）：
两个链表都是逆序存储数字的，即两个链表的个位数、⼗位数等都已经对应，可以直接相加。 在相加过程中，我们要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加。如果产⽣进位的位置在链表尾部，即答案位数⽐原链表位数⻓⼀位，还需要再 new ⼀个结点储存最⾼位。 - 代码示例：
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：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
⽰例 2：
输⼊：head = []
输出：[]
⽰例 3：
输⼊：head = [1]
输出：[1]
提⽰：
链表中节点的数⽬在范围 [0, 100] 内 0 <= Node.val <= 100
-
解法（模拟）：
算法思路：通过画图模拟算法！ -
代码示例：
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;
}
三、重排链表
- 题目链接：重排链表
- 题目描述：
给定⼀个单链表 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
-
解法：
算法思路：
找中间节点；
中间部分往后的逆序；
合并两个链表 -
代码示例：
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个升序链表
- 题目链接：合并K个升序链表
- 题目描述：
给你⼀个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到⼀个升序链表中，返回合并后的链表。
⽰例 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
-
解法⼀（利用堆）：
算法思路：
合并两个有序链表是比较简单且做过的，就是⽤双指针依次比较链表 1 、链表 2 未排序的最⼩元 素，选择更小的那⼀个加⼊有序的答案链表中。 合并 K 个升序链表时，我们依旧可以选择 K 个链表中，头结点值最小的那⼀个。那么如何快速的得 到头结点最小的是哪⼀个呢？⽤堆这个数据结构就好啦~ 我们可以把所有的头结点放进⼀个⼩根堆中，这样就能快速的找到每次 K 个链表中，最小的元素是哪个。 -
代码示例：
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个⼀组翻转链表
- 题目链接：K个⼀组翻转链表
- 题目描述：
给你链表的头节点 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
- 解法（模拟）：
算法思路：
本题的⽬标⾮常清晰易懂，不涉及复杂的算法，只是实现过程中需要考虑的细节比较多。 我们可以把链表按 K 个为⼀组进⾏分组，组内进⾏反转，并且记录反转后的头尾结点，使其可以和 前、后连接起来。思路⽐较简单，但是实现起来是⽐较复杂的。
我们可以先求出⼀共需要逆序多少组（假设逆序 n 组），然后重复 n 次⻓度为 k 的链表的逆序即 可。 - 代码示例：
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;
}
结语
本文到这里就结束了，主要介绍了链表算法，并通过几道例题更加深入了解链表算法相关知识，重点在于画图理清题目思路，注重代码细节。希望能够对你有帮助！
以上就是本文全部内容，感谢各位能够看到最后，创作不易，希望大家多多支持！
最后，大家再见！祝好！我们下期见！