前面我们刚刚学习数据结构时，已经刷了许多与链表相关的算法了。这里还刷一些作为补充。注意：所有与链表相关的题目都是属于模拟题。因为其会给我们提供一种模拟的思路来写。
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- 题目数据保证列表表示的数字不含前导零
思路：题目是让我们把链表中的两个数相加为一个数，并将这个数也转换为链表的形式。这是一道简单的模拟题。定义一个变量记录当前位数相加的结果，存储到新的链表节点中，这里在存储时一定得是小于10的数，处理方式是：%10，经过这次处理后再 /10 即可。
代码实现：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 创建虚拟头节点
ListNode head = new ListNode(-1);
// 申请三个指针针对后续修改
ListNode cur1 = l1, cur2 = l2, cur = head;
// 保存当前两数之和的值
int sum = 0;
while (cur1 != null && cur2 != null) {
// 求和
sum += cur1.val;
sum += cur2.val;
// 构造新节点
cur.next = new ListNode(sum % 10);
// 更新 sum cur cur1 cur2 的值
sum /= 10;
cur = cur.next;
cur1 = cur1.next;
cur2 = cur2.next;
}
// 可能cur1 != null 也可能 cur2 != null
while (cur1 != null) {
// 求和
sum += cur1.val;
// 构造新节点
cur.next = new ListNode(sum % 10);
// 更新 sum cur cur1
sum /= 10;
cur = cur.next;
cur1 = cur1.next;
}
while (cur2 != null) {
// 求和
sum += cur2.val;
// 构造新节点
cur.next = new ListNode(sum % 10);
// 更新 sum cur cur2
sum /= 10;
cur = cur.next;
cur2 = cur2.next;
}
// 可能还会存在进位
if (sum != 0) {
cur.next = new ListNode(sum % 10);
}
return head.next;
}
}24.两两交换链表中的节点
题目：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例 2：
输入：head = [] 输出：[]示例 3：
输入：head = [1] 输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内0 <= Node.val <= 100
思路：本题也是模拟题，对于模拟题，我们只需要大胆的将过程模拟出来，并用代码表示一下，整个题目也就迎刃而解了。
注意：在处理链表相关的问题时，创建虚拟头节点非常有利于我们去处理相关问题，而不需要去考虑边界情况。在本题中，如果我们没有创建虚拟头节点，则针对第一组的修改与后续的修改是不同的逻辑。
代码实现：
class Solution {
public ListNode swapPairs(ListNode head) {
// 处理特殊情况
if (head == null || head.next == null) {
return head;
}
// 创建哨兵位节点
ListNode newHead = new ListNode(-1, head);
// 申请四个结点指针
ListNode n1 = newHead, n2 = head, n3 = n2.next, n4 = n3.next;
while (n2 != null && n3 != null) {
// 修改节点指针指向(n1的修改得在n3之前)
n1.next = n3;
n3.next = n2;
n2.next = n4;
// 更新节点指针
n1 = n2;
n2 = n4;
n3 = n4 == null ? null : n4.next;
n4 = n3 == null ? null : n3.next;
}
return newHead.next;
}
}143.重排链表
题目：
给定一个单链表
L的头节点head，单链表L表示为：L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 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 * 104]1 <= node.val <= 1000
思路：本题如果采用普通的模拟策略，会发现非常复杂。因为我们得先找到尾节点，然后与头节点一同插入新链表中，接着一直重复上述的操作，非常的麻烦。本题算是一个链表的综合题，结合了 快慢双指针法+逆序链表法+合并两个链表法 三个操作于一身。先得通过快慢双指针法找到链表的中间结点，然后从中间结点开始逆序后面的结点，最后将原来的链表与逆序后的新链表执行合并两个链表的操作即可。
注意：
1、在逆序的时候，我们有两种选择：1）将slow后面的部分逆序；2）将slow包含在内的部分都进行逆序。上面的两种方式都是可以的。
2、 在合并两个链表时，什么情况下才算结束呢？当然是两个链表都没有遍历完成时，但是原链表的尾节点（除去逆序之后的尾节点）并不是为null，因此无法判断，我们得再逆序之前就先将原链表的尾节点处理干净。
代码实现：
class Solution {
public void reorderList(ListNode head) {
// 处理边界情况(少于两个节点时，无需去重排)
if (head == null || head.next == null || head.next.next == null) {
return;
}
// 1、先找到中间结点
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2、将 slow 后面的结点进行逆序
ListNode cur = slow.next;
slow.next = null; // 分割成两个链表
ListNode next = cur.next, prev = null;
while (cur != null) {
// 修改指针指向
cur.next = prev;
// 更新指针
prev = cur;
cur = next;
next = next == null ? null : next.next;
}
// 3、合并两个链表
cur = head;
ListNode newHead = new ListNode(-1), ret = newHead;
while (prev != null) { // 这里一定是逆序链表先遍历完成
// 先插入原链表节点
ret.next = cur;
// 更新指针（原链表、新链表）
ret = cur;
cur = cur.next;
// 再插入逆序链表节点
ret.next = prev;
// 更新指针(逆序链表、新链表)
ret = prev;
prev = prev.next;
}
// 将原链表后的结点插入新链表即可
ret.next = cur;
head = newHead.next;
}
}23.合并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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
思路：暴力解法：可以将合并两个有序链表的方式来合并K个升序链表，循环K次，每次都合并两个有序链表，最后剩下的链表就是合并K个链表之后的结果。这里之所以是暴力解法，是因为我们每次都是取其中两个链表来合并，那如果我们每次将全部的链表数组的节点都取出来比较呢？那最终不就只需要循环最长的链表长度次数了吗？时间复杂度就下降了不少。那该怎么实现呢？我们可以先使用最小堆将链表的头节点入堆，每次从堆中拿到一个最小值，然后继续往后插入，直至最终堆为空才停止。
代码实现：
暴力解法：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 将k个链表的合并顺序按照一个一个的
ListNode ret= null;
for (int i = 0; i < lists.length; i++) {
ret = mergeTwoLists(ret, lists[i]);
}
return ret;
}
// 合并两个有序链表
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 处理特殊情况
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode newHead = new ListNode(-1);
ListNode cur1 = l1, cur2 = l2, cur = newHead;
// 处理两个链表都不为空的情况
while (cur1 != null && cur2 != null) {
if (cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
} else {
cur.next = cur2;
cur2 = cur2.next;
}
cur = cur.next;
}
// 处理一个链表不为空的情况
if (cur1 != null) {
cur.next = cur1;
}
if (cur2 != null) {
cur.next = cur2;
}
return newHead.next;
}
}优先级队列优化：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 使用优先级队列来排序
return mergeKLists_Heap(lists);
}
private ListNode mergeKLists_Heap(ListNode[] lists) {
// 排除特殊情况
if (lists == null) {
return null;
}
// 1、创建一个优先级队列，并定义比较规则（最小堆）
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val-b.val);
// 2、先将所有链表的头节点存放到优先级队列中
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
heap.offer(lists[i]);
}
}
// 3、开始合并链表
ListNode newHead = new ListNode(-1);
ListNode cur = newHead;
while (!heap.isEmpty()) {
// 拿到当前最小的元素，并插入新链表
ListNode min = heap.poll();
cur.next = min;
// 更新节点指针与堆
cur = cur.next;
if (min.next != null) {
heap.offer(min.next);
}
}
return newHead.next;
}
}还可以使用分治的思想来解决。可以把这里的链表看成是一个一个的元素，采取归并排序的思路来处理，其实本质上还是合并两个有序链表。
代码实现：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 使用递归的方式来处理
return merge(lists, 0, lists.length-1);
}
private ListNode merge(ListNode[] lists, int start, int end) {
// 处理边界情况
if (start > end) { // 不存在链表
return null;
}
if (start == end) { // 只有一个链表
return lists[start];
}
// 1、递归分解
int mid = (start + end) / 2;
ListNode l1 = merge(lists, start, mid);
ListNode l2 = merge(lists, mid+1, end);
// 2、合并两个有序链表
ListNode newHead = new ListNode(-1);
ListNode cur = newHead, cur1 = l1, cur2 = l2;
// 处理两者都有的情况
while (cur1 != null && cur2 != null) {
if (cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
} else {
cur.next = cur2;
cur2 = cur2.next;
}
cur = cur.next;
}
// 处理单独一个链表的情况
if (cur1 != null) {
cur.next = cur1;
}
if (cur2 != null) {
cur.next = cur2;
}
return newHead.next;
}
}25.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]提示：
- 链表中的节点数目为
n1 <= k <= n <= 50000 <= Node.val <= 1000
思路：本题也是根据思路来模拟，先求出需要翻转的组数，在循环组数去翻转链表即可。
代码实现：
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 1、计算需要反转的次数
ListNode cur = head;
int n = 0, cnt = 0;
while (cur != null) {
cnt++;
cur = cur.next;
}
n = cnt / k;
// 2、开始n次翻转，每次翻转k个
ListNode newHead = new ListNode(-1);
ListNode prev = head, next = prev.next, tmp = null;
for (int i = 0; i < n; i++) {
cur = cur == null ? newHead : tmp; // 记录需要头插的位置
for (int j = 0; j < k; j++) {
if (j == 0) {
tmp = prev; // 记录下一次头插的位置
}
// 使用头插法
prev.next = cur.next;
cur.next = prev;
// 更新节点指针(cur不能更新)
prev = next;
next = next == null ? null : next.next;
}
}
cur = tmp; // 确保cur为新链表的尾节点
// 3、将剩下的结点拼接上去
cur.next = prev;
return newHead.next;
}
}好啦！本期 常见链表专题相关算法 的学习之旅 就到此结束啦！我们下一期再一起学习吧！
