励志：
🚩 半身浸江，全身如林，所谓万丈深渊，下去也是前程万里。我启程了，你呢?
一、单向链表
1. 链表操作
1.1 链表旋转
题：61. 旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
提示：
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109
解：
📖 解题思路：
- 得到链表长度len
- 指针p指向第n - k节点
- 修改head，p，tail 的next指向
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k == 0) return head; // 判空
ListNode tail = head;
// 链表长度
int len = 1;
while(tail.next != null){
tail = tail.next;
len ++;
}
// 第n-K节点
k %= len;
ListNode p = head;
for(int i = 1; i <= len - k - 1; i ++) p = p.next;
// 修改指针指向
tail.next = head;
head = p.next;
p.next = null;
return head;
}
}- 时间复杂度：时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次。
- 空间复杂度：O(1)，我们只需要常数的空间存储若干变量。
题：25. K 个一组翻转链表
给你一个链表，每 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]示例 3：
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]示例 4：
输入：head = [1], k = 1
输出：[1]提示：
列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz
解：
📖 解题思路： 反转链表
- 首加一个空（减少判空，便于return）
- 翻转指针（pre，start，end，next）
- 反转链表模板（三人行）
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 首加一个空节点(1.减少判断 2.返回节点)
ListNode preTemp = new ListNode();
preTemp.next = head;
// 翻转区间（start，end）
ListNode pre = preTemp;
ListNode start = pre;
ListNode end = pre;
ListNode next = end.next;
while(end.next != null) {
// 判断是否还可以继续翻转
for(int i = 0; i < k; i ++){
end = end.next;
if(end == null) return preTemp.next;
}
start = pre.next;
next = end.next;
// 断链
end.next = null;
// 接链（此时end在前，start在后）
pre.next = reverse(start);
start.next = next;
// start, end重新归位
pre = start;
end = pre;
}
return preTemp.next;
}
// 反转链表模板
ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}- 时间复杂度：O(n)，其中 n 为链表的长度。
- 空间复杂度：O(1)，常数个变量。
1.2 链表相交
题：面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
解：
📖 解题思路：双指针
走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。思想： 1+2 = 2+1
没有交点的情况可以约化为 交点为 None 的情况。（即将两链表末端的 None 看作交点）
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(A != B){
A = A != null ? A.next : headB;
B = B != null ? B.next : headA;
}
return A;
}
}- 时间复杂度 O(a + b) ： 最差情况下（即 |a - b| = 1 , c = 0），此时需遍历 a + b 个节点。
- 空间复杂度 O(1) ： 节点指针 A , B 使用常数大小的额外空间。
以下题目一样，不再赘述了。
题：剑指 Offer 52. 两个链表的第一个公共节点
题：160. 相交链表
题：剑指 Offer II 023. 两个链表的第一个重合节点
📖 另解：哈希
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visit = new HashSet<>();
// 遍历A
ListNode temp = headA;
while(temp != null) {
visit.add(temp);
temp = temp.next;
}
// 遍历B
temp = headB;
while(temp != null) {
if(visit.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}1.3 链表归并
题：21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = []
输出：[]示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列解：
📖 解题思路：递归
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// l1 or l2 遍历结束
if(l1 == null) return l2;
if(l2 == null) return l1;
// 合并
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}
}时间复杂度：O(n+m)，其中n，m分别为链表长度。
空间复杂度：O(n+m)，其中n，m分别为链表长度。
📖 另解：迭代
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode preTmp = new ListNode(); // 伪头结点
ListNode node = preTmp;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
node.next = l1;
l1 = l1.next;
}else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
// 合并未完成的
node.next = l1 == null ? l2 : l1;
return preTmp.next;
}
}题：剑指 Offer 25. 合并两个排序的链表
题：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.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4解：
📖 解题思路：朴素解法（正常合并）
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = null;
for(ListNode list : lists) {
res = mergeTwoList(res, list);
}
return res;
}
ListNode mergeTwoList(ListNode A, ListNode B) {
// 伪头结点, 虚拟链
ListNode preTemp = new ListNode();
// 指针
ListNode node = preTemp;
while(A != null && B != null) {
if(A.val < B.val) {
node.next = A;
A = A.next;
}else {
node.next = B;
B = B.next;
}
node = node.next;
}
node.next = A != null ? A : B;
return preTemp.next;
}
}- 时间复杂度：O（k^2 * n）
- 空间复杂度：O（1）
📖 解题思路：二分
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
ListNode merge(ListNode[] lists, int l, int r) {
// 出口
if(l == r) return lists[l]; // 这个很重要
if(l > r) return null;
// 递归划分
int m = (l + r) >> 1;
ListNode A = merge(lists, l, m);
ListNode B = merge(lists, m + 1, r);
// 合并
return mergeTwoList(A, B);
}
ListNode mergeTwoList(ListNode A, ListNode B) {
// 伪头结点, 虚拟链
ListNode preTemp = new ListNode();
// 指针
ListNode node = preTemp;
while(A != null && B != null) {
if(A.val < B.val) {
node.next = A;
A = A.next;
}else {
node.next = B;
B = B.next;
}
node = node.next;
}
node.next = A != null ? A : B;
return preTemp.next;
}
}- 时间复杂度：O（kn * log k）二分使用后 k → log k
- 空间复杂度：O（log k）二分使用后，递归栈空间log k
📖 解题思路：优先队列
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 优先队列(小顶堆)(先储存各链表的头结点)
Queue<ListNode> priQueue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
for(ListNode list : lists) {
if(list != null) { // 注意这里不为空
priQueue.offer(list);
}
}
// 伪头结点
ListNode preTemp = new ListNode();
// 指针
ListNode temp = preTemp;
// 遍历堆
while(!priQueue.isEmpty()) {
ListNode min = priQueue.poll();
temp.next = min;
temp = temp.next;
if(min.next != null) {
priQueue.offer(min.next);
}
}
return preTemp.next;
}
}- 时间复杂度：O（kn * log k）
- 空间复杂度：O（log k）
题：剑指 Offer II 078. 合并排序链表
题：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解：
📖 解题思路：双指针 + 线性表
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if (head == null) return;
// 线性表
List<ListNode> list = new ArrayList<>();
ListNode temp = head;
while(temp != null) {
list.add(temp);
temp = temp.next;
}
// 双指针
int i = 0, j = list.size() - 1;
while(i < j) {
list.get(i).next = list.get(j);
i ++;
if(i == j) break;
list.get(j).next = list.get(i);
j --;
}
list.get(i).next = null;
}
}- 时间复杂度：O（N），N为链表的节点数，遍历链表
- 空间复杂度：O（N），N为链表的节点数，线性表占用空间N
解题思路：寻找链表中点 + 链表逆序 + 合并链表
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if(head == null) return;
ListNode mid = midNode(head);
ListNode l2 = reverList(mid.next);
mid.next = null;
mergeList(head, l2);
}
// 找中点（快慢指针）
ListNode midNode(ListNode node) {
ListNode p = node;
ListNode q = node;
while(q.next != null && q.next.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
// 反转链表（三人行）
ListNode reverList(ListNode node) {
ListNode pre = null;
ListNode cur = node;
while(cur != null) {
// 松手先保存
ListNode nextTemp = cur.next;
// 松手
cur.next = pre;
// 指针前移
pre = cur;
cur = nextTemp;
}
return pre;
}
// 合并链表
void mergeList(ListNode A, ListNode B) {
ListNode A_next;
ListNode B_next;
while(A != null && B != null) {
A_next = A.next;
A.next = B;
A = A_next;
B_next = B.next;
B.next = A;
B = B_next;
}
}
}- 时间复杂度：O（N）， N为链表节点
- 空间复杂度：O（1）
1.4 链表排序
题：148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
- 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105解：
解题思路：自顶向下归并排序
- 找中点（快慢双指针）
- 链表排序
- 合并排序链表
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
// 链表排序(二分法)
public ListNode sortList(ListNode head, ListNode tail) {
// 递归出口(节点个数 == 0 、1)
if(head == null || head.next == null) return head;
ListNode mid = mid(head);
ListNode node = mid.next; // 松手前先保存
mid.next = null;
ListNode L1 = sortList(head, mid);
ListNode L2 = sortList(node, tail);
return merge(L1, L2);
}
// 找中点
ListNode mid(ListNode head) {
ListNode p = head;
ListNode q = head;
while(q.next != null && q.next.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
// 链表合并(递归法)
ListNode merge(ListNode A, ListNode B) {
if(A == null) return B;
if(B == null) return A;
if(A.val < B.val) {
A.next = merge(A.next, B);
return A;
}else {
B.next = merge(A, B.next);
return B;
}
}
}- 时间复杂度：O（N logN），N为链表长度
- 空间复杂度：O（logN），N为链表长度
解题思路：自底向上归并排序
- 链表长度
- 链表拆分与合并（步长 << 2 切分））
注意：拆分保证两条链独立，并临时保存要拼接的节点 ==（分手先保存。合并要纯粹）==
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
// 链表为空或链表只剩一个节点
if(head == null || head.next == null) return head;
// 伪头结点
ListNode node = new ListNode();
node.next = head;
// 链表长度
int len = 0;
ListNode temp = head;
while(temp != null) {
len ++;
temp = temp.next;
}
// 遍历
for(int i = 1; i < len; i <<= 1) { // i 为步数，步数指数翻倍
// 即将分手的pre，cur(指针)
ListNode pre = node;
ListNode cur = node.next;
while(cur != null) { // 还能分手吗？
// 分割链, A链， B链
ListNode A = cur;
ListNode B = splitList(A, i);
// cur先复位，再合并对接（合并要保证两链独立）
cur = splitList(B, i); // cur 复位
pre.next = mergeList(A, B); // pre 对接
while(pre.next != null) { // pre复位
pre = pre.next;
}
}
}
return node.next;
}
// 分割得到链表A，B，拿到B的头结点
ListNode splitList(ListNode head, int step) {
if(head == null) return null;
for(int i = 1; i < step && head.next != null; i ++) {
head = head.next;
}
// 保存
ListNode res = head.next;
// 松手
head.next = null;
return res;
}
// 合并，迭代法
ListNode mergeList(ListNode A, ListNode B) {
// 伪头结点
ListNode preTemp = new ListNode();
// 哨兵
ListNode node = preTemp;
while(A != null && B != null) {
if(A.val < B.val) {
node.next = A;
A = A.next;
}else {
node.next = B;
B = B.next;
}
node = node.next;
}
// 判空
node.next = A != null ? A : B;
return preTemp.next;
}
}时间复杂度：O（N logN）
空间复杂度：O（1）
题：剑指 Offer II 077. 链表排序
1.5 链表回文
题：234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解：
解题思路：
- 找中点
- 翻转一半
- 比对
- 还原（可有可无）
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
// 找中点 1=>1 123=>2 1234=>2
ListNode A_end = mid(head);
ListNode B_start = A_end.next;
A_end.next = null;
// 翻转后半部分
B_start = reverse(B_start);
// 比对
boolean res = compare(head, B_start);
// 还原
A_end.next = reverse(B_start);
return res;
}
// 链表找中点，快慢指针法
ListNode mid(ListNode head) {
ListNode p = head;
ListNode q = head;
while(q.next != null && q.next.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
// 链表反转模板
ListNode reverse(ListNode head) { // 三人行模板
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode temp = cur.next; // 松手先保存
cur.next = pre;
pre = cur; // 归位
cur = temp;
}
return pre;
}
// 链表比对模板(len(B) <= len(A))
boolean compare(ListNode A, ListNode B) {
while(B != null) {
if(A.val != B.val) return false;
A = A.next;
B = B.next;
}
return true;
}
}- 时间复杂度：O（N）：N为链表长度
- 空间复杂度：O（1）：只修改链表的指向
题：剑指 Offer II 027. 回文链表
题：面试题 02.06. 回文链表
1.6 链表逆序
题：剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000解：
解题思路：辅助栈
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
Stack<Integer> stack = new Stack<>();
while(head != null) {
stack.push(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i ++) {
res[i] = stack.pop();
}
return res;
}
}- 时间复杂度：O（N），遍历链表
- 空间复杂度：O（N）, 额外使用一个栈来存储链表中的每一个节点
另解：递归（与上面解法本质一样）
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
ArrayList<Integer> list = new ArrayList<>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[list.size()];
for(int i = 0; i < res.length; i ++) {
res[i] = list.get(i);
}
return res;
}
void recur(ListNode head) {
if(head == null) return;
recur(head.next); // 先递归
list.add(head.val); // 然后添加
}
}题：剑指 Offer 24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000解：
解题思路：反转模板
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 三人行
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode temp = cur.next; // 松手
cur.next = pre;
// 归位
pre = cur;
cur = temp;
}
return pre;
}
}- 时间复杂度：O（N）：遍历链表，N为链表长度
- 空间复杂度：O（1）：指针常量
另解：递归
规避递归细节，找递推公式！
eg. 1->2->3->null ==> null<-1<-2<-3
- fun（node1）= fun（node2） + ？
- ？ = 2->1 + 1->null
AC代码：
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) { //终止条件并不难想
return head;
}
ListNode node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node; //按上面的例子，F(node=1)和F(node=2)它俩反转后的头节点是同一个
}题：206. 反转链表
题：剑指 Offer II 024. 反转链表
题：445. 两数相加 II
给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
提示：
链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。
解：
解题思路：栈
- 逆序=>栈 O（N）、反转 O（1）
- 进位判断（/10=进位 %10=本位）
- 双指针倒指（null <- A <- B ...）
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> A = new Stack<>();
Stack<Integer> B = new Stack<>();
// 入栈
while(l1 != null) {
A.push(l1.val);
l1 = l1.next;
}
while(l2 != null) {
B.push(l2.val);
l2 = l2.next;
}
ListNode res = null;
int nextDigit = 0; // 进位
while(!A.isEmpty() || !B.isEmpty() || nextDigit != 0) {
int a = A.isEmpty() ? 0 : A.pop(); // 弹出先判空，防止空指针
int b = B.isEmpty() ? 0 : B.pop();
int c = a + b + nextDigit;
nextDigit = c / 10;
c = c % 10;
ListNode temp = new ListNode(c);
temp.next = res; // 放在第一位
res = temp; // res指针前移
}
return res;
}
}- 时间复杂度：O（max（m，n））：m，n分别为链表a，b长度，最坏遍历完最长链表
- 空间复杂度：O（m + n）：m，n分别为链表a，b长度，最坏链表每次相加后都进位
另解：反转链表
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 反转l1，l2
l1 = reverse(l1);
l2 = reverse(l2);
// 正向指针
ListNode preHead = new ListNode(); // 伪头结点
ListNode node = preHead; // 指针，操作链表
int nextDigit = 0; // 进位
// 链表相加
while(l1 != null || l2 != null || nextDigit != 0) {
int sum = nextDigit;
if(l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if(l2 != null) {
sum += l2.val;
l2 = l2.next;
}
nextDigit = sum / 10;
sum = sum % 10;
// 进位规则：往右进位
ListNode temp = new ListNode(sum);
node.next = temp;
node = node.next;
}
return reverse(preHead.next);
}
ListNode reverse(ListNode head) {
// 三人行模板
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode temp = cur.next; // 松手先保存
cur.next = pre;
// 指针归位
pre = cur;
cur = temp;
}
return pre;
}
}题：剑指 Offer II 025. 链表中的两数相加
题：92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？解：
解题思路：穿针引线法
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 伪头节点
ListNode preHead = new ListNode();
preHead.next = head;
// leftNode(2) -> start(3) -> end(5) -> rightNode(6)
ListNode leftNode = preHead;
for(int i = 0; i < left - 1; i ++) {
leftNode = leftNode.next;
}
ListNode start = leftNode.next;
ListNode end = leftNode;
for(int i = 0; i < right - left + 1; i ++) {
end = end.next;
}
ListNode rightNode = end.next;
// 断链
leftNode.next = null;
end.next = null;
// 反转 + 拼接
leftNode.next = reverse(start);
start.next = rightNode;
return preHead.next;
}
// 反转模板
ListNode reverse(ListNode head) {
// 三人行模板
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
// 松手先保存
ListNode temp = cur.next;
cur.next = pre;
// 指针归位
pre = cur;
cur = temp;
}
return pre;
}
}- 时间复杂度：O（N）N为链表长度，最坏长度遍历整个链表。
- 空间复杂度：O（1）用到四个指针常量。
另解：头插法 + 穿针引线
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 伪头节点
ListNode dummyNode = new ListNode();
dummyNode.next = head;
// 三人行 pre(), cur(), next();
ListNode pre = dummyNode;
for(int i = 0; i < left - 1; i ++) {
pre = pre.next;
}
// 头插法
ListNode cur = pre.next;
ListNode next;
for(int i = 0; i < right - left; i ++) { // 第一个不需要操作，所以直接len(r-f)-1
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummyNode.next;
}
}2. 链表结点操作
2.1 链表结点删除
题：剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意： 此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
解：
解题思路：双指针
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head.val == val) return head.next;
// cur:待删除的节点 pre:删除节点的上一个
ListNode pre = head;
ListNode cur = pre.next;
while(cur != null && cur.val != val) {
pre = cur;
cur = cur.next;
}
if(cur != null) pre.next = cur.next;
return head;
}
}- 时间复杂度：O（N）
- 空间复杂度：O（1）
题：237. 删除链表中的节点
请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应 变为 4 -> 5 -> 9示例 3：
输入：head = [1,2,3,4], node = 3
输出：[1,2,4]示例 4：
输入：head = [0,1], node = 0
输出：[1]示例 5：
输入：head = [-3,5,-99], node = -3
输出：[5,-99]
提示：
链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是唯一的
需要删除的节点 node 是 链表中的一个有效节点 ，且 不是末尾节点
解：
解题思路：狸猫换太子
我们不知道前一节点，无法直接删除操作，那就将要删除节点的next节点==赋值==给删除节点，==转化为删除next节点==。
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
// 将自己复制成下一个节点
node.val = node.next.val;
// 自己的下一节点指向下下个
node.next = node.next.next;
}
}- 时间复杂度：O（1）
- 空间复杂度：O（1）
题：19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1
输出：[]示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
解：
解题思路：双指针
- 伪头结点，前后指针
- 终点：前=待删除结点上一个 后=null（末尾）
- 起点：前 =伪头结点 后=伪 + n
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode();
dummy.next = head;
// 前后指针
ListNode p = dummy;
ListNode q = head;
for(int i = 0; i < n; i ++) {
q = q.next;
}
while(q != null) {
p = p.next;
q = q.next;
}
p.next = p.next.next;
return dummy.next;
}
}- 时间复杂度：O（N） 遍历链表，N为链表长度
- 空间复杂度：O（1）指针常量
题：剑指 Offer II 021. 删除链表的倒数第 n 个结点
题：237. 删除链表中的节点
题：82. 删除排序链表中的重复元素 II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
解：
解题思路：双指针
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1, head);
// 双指针
ListNode p = dummy;
ListNode q = head;
while(q != null) {
boolean flag = false;
while(q.next != null && q.val == q.next.val) {
flag = true;
q = q.next;
}
if(flag) {
p.next = q.next;
}else {
p = p.next;
}
q = q.next;
}
return dummy.next;
}
}- 时间复杂度：O（N），N为链表长度
- 空间复杂度：O（1），指针消耗
另解：
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
// 可能会删除头结点
ListNode dummy = new ListNode(-1, head);
// 对下一个和下下个比较val
ListNode cur = dummy;
while(cur.next != null && cur.next.next != null) {
if(cur.next.val == cur.next.next.val) {
int x = cur.next.val;
while(cur.next != null && cur.next.val == x) {
cur.next = cur.next.next;
}
}else {
cur = cur.next;
}
}
return dummy.next;
}
}题：83. 删除排序链表中的重复元素
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
解：
:chestnut:解题思路：遍历
- 当头结点重复，可以删除第二个，这样头结点必不删除，不用设伪头结点
- 删除节点，cur指向上一个，cur.next 需判空再比较
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}- 时间复杂度：O（n）
- 空间复杂度：O（1）
题：203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]示例 2：
输入：head = [], val = 1
输出：[]示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
解：
解题思路：
- 头结点删除 => 加入伪头结点
- 删除元素 => 拿到上一个节点，while(cur.next)
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
ListNode dummy = new ListNode(-1, head);
ListNode cur = dummy;
while(cur.next != null) {
if(cur.next.val == val) {
cur.next = cur.next.next;
}else {
cur = cur.next;
}
}
return dummy.next;
}
}- 时间复杂度：O（n）
- 空间复杂度：O（1）
题：1171. 从链表中删去总和值为零的连续节点
给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
示例 1：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。示例 2：
输入：head = [1,2,3,-3,4]
输出：[1,2,4]示例 3：
输入：head = [1,2,3,-3,-2]
输出：[1] 提示：
给你的链表中可能有 1 到 1000 个节点。
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.
解：
解题思路：前缀和
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
if(head == null) return head;
// 头结点可能被删除 => 引入伪头结点
ListNode dummy = new ListNode(0, head);
// HashMap记录前缀和，重复记录最后一次
int sum = 0;
HashMap<Integer, ListNode> map = new HashMap<>();
for(ListNode i = dummy; i != null; i = i.next) {
sum += i.val;
map.put(sum, i);
}
// 二次遍历，删除前缀和相等的区间
sum = 0;
for(ListNode i = dummy; i != null; i = i.next) {
sum += i.val;
i.next = map.get(sum).next;
}
return dummy.next;
}
}- 时间复杂度：O（N），N为链表长度，遍历链表
- 空间复杂度：O（N），hashMap所占空间
2.2 链表结点索引
题：剑指 Offer 22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.解：
解题思路：双指针
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null) return head;
ListNode p = head, q = head;
for(int i = 0; i < k; i ++) {
p = p.next;
}
while(p != null) {
p = p.next;
q = q.next;
}
return q;
}
}- 时间复杂度：O（N），N为链表长度，p走了N步，q走了N - k
- 空间复杂度：O（1），双指针使用了额外的空间
题：面试题 02.02. 返回倒数第 k 个节点
题：876. 链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
解：
解题思路：快慢指针
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null || head.next == null) return head;
ListNode p = head, q = head;
while(q != null && q.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
}- 时间复杂度：O（N），N为链表长度
- 空间复杂度：O（1），常数空间存放指针
题：1019. 链表中的下一个更大节点
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例 1：
输入：[2,1,5]
输出：[5,5,0]示例 2：
输入：[2,7,4,3,5]
输出：[7,0,5,5,0]示例 3：
输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]
提示：
对于链表中的每个节点，1 <= node.val <= 10^9
给定列表的长度在 [0, 10000] 范围内
解：
解题思路：单增栈
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> list = new ArrayList<>();
while(head != null) {
list.add(head.val);
head = head.next;
}
// 单增栈
Stack<Integer> stack = new Stack<>();
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i ++) {
while(!stack.isEmpty() && list.get(stack.peek()) < list.get(i)) {
int index = stack.pop();
res[index] = list.get(i);
}
stack.push(i);
}
return res;
}
}- 时间复杂度：O（N），遍历列表，链表
- 空间复杂度：O（N），栈、列表各占用N空间，N为链表长度
2.2 链表结点交换
题：24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]示例 2：
输入：head = []
输出：[]示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
解：
解题思路：
递归步骤：
- 单个递归的核心步骤
- 递归间的连接点
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 判空，或者一个
if(head == null || head.next == null) return head;
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}- 时间复杂度：O（N），N为链表长度
- 空间复杂度：O（N），N为链表长度
另解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
// 需要操作头
ListNode dummy = new ListNode(0, head);
ListNode temp = dummy;
while(temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummy.next;
}
}题：1721. 交换链表中的节点
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[1,4,3,2,5]示例 2：
输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]示例 3：
输入：head = [1], k = 1
输出：[1]示例 4：
输入：head = [1,2], k = 1
输出：[2,1]示例 5：
输入：head = [1,2,3], k = 2
输出：[1,2,3]
提示：
链表中节点的数目是 n
1 <= k <= n <= 105
0 <= Node.val <= 100
解：
解题思路：值交换
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode left = dummy;
for(int i = 0; i < k; i ++) left = left.next;
ListNode right = dummy;
ListNode cur = left;
while(cur != null) {
right = right.next;
cur = cur.next;
}
int value = left.val;
left.val = right.val;
right.val = value;
return head;
}
}- 时间复杂度：O（N）
- 空间复杂度：O（1）
解题思路：`节点交换
AC代码：
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;// 因为头结点可能会发生交换，所以要构造一个哑结点
ListNode pre1 = dummy;// pre1指向第k个节点的前一个节点
ListNode left = dummy.next;// 第k个节点
ListNode pre2 = dummy;// pre2指向倒数第k个节点的前一个节点
ListNode right = dummy.next;// 倒数第k个节点
for(int i = 1; i < k; i++){
pre1 = pre1.next;
left = left.next;
}
ListNode cur = left;
ListNode temp = left.next;// 第k个节点的后一个节点
while(cur.next != null){
pre2 = pre2.next;
right = right.next;
cur = cur.next;
}
if(right == pre1){// 特殊情况，倒数第k个节点在第k个节点的左侧
right.next = temp;
left.next = right;
pre2.next = left;}
else{
left.next = right.next;
if(pre2 == left){right.next = left;}// 特殊情况，第k个节点在倒数第k个节点的左侧
else{
pre2.next = left;
right.next = temp;
}
pre1.next = right;
}
return dummy.next;
}
}二、双向链表
1.1 扁平化链表
题：430. 扁平化多级双向链表
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：
输入的多级列表如下图所示：
扁平化后的链表如下图：
示例 2：
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：
输入的多级列表如下图所示：
1---2---NULL
|
3---NULL示例 3：
输入：head = []
输出：[]
如何表示测试用例中的多级链表？
以 示例 1 为例：
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL序列化其中的每一级之后：
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]合并所有序列化结果，并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
提示：
节点数目不超过 1000
1 <= Node.val <= 10^5
解：
解题思路：递归
AC代码：
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
// 伪头结点
Node dummy = new Node(0);
dummy.next = head;
while(head != null) {
if(head.child == null){
head = head.next;
}else {
Node temp = head.next; // 松手先保存
// 递归
Node dfsChild = flatten(head.child);
head.next = dfsChild;
head.child = null;
dfsChild.prev = head;
// head 移动到dfsChile末尾
while(head.next != null) head = head.next;
head.next = temp;
if(temp != null) temp.prev = head;
head = head.next;
}
};
return dummy.next;
}
}- 时间复杂度：O（N ^2^）
- 空间复杂度：O（N）
解题思路：递归优化
由于我们递归处理head.child后不得不在找当前层的尾结点，导致算法时间度O（N ^2^）
可行性优化：额外设计一个dfs用于返回扁平化链表尾结点
AC代码：
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
dfs(head);
return head;
}
Node dfs(Node head) {
// 最后一个节点指针
Node last = head;
while(head != null) {
if(head.child == null) {
// 分别移动last、head指针
last = head;
head = head.next;
}else {
// 松手先保存
Node temp = head.next;
Node childLast = dfs(head.child);
head.next = head.child;
head.child.prev = head;
head.child = null;
if(childLast != null) childLast.next = temp;
if(temp != null) temp.prev = childLast;
// 指针移动
last = head;
head = childLast;
}
}
return last;
}
}- 时间复杂度：O（N）
- 空间复杂度：O（N）
三、循环链表
1.1 链表排序
题：剑指 Offer II 029. 排序的循环链表
给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。
给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
示例 1：
输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。
示例 2：
输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。示例 3：
输入：head = [1], insertVal = 0
输出：[1,0]
提示：
0 <= Number of Nodes <= 5 * 10^4
-10^6 <= Node.val <= 10^6
-10^6 <= insertVal <= 10^6
解：
解题思路：
- 画图分析:找到max(最后一个)，min
- 分两种情况 [min,max]区间 内外
- 区间外：max.next = insertVal
区间内：移动min，min.next = insertVal
AC代码：
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _next) {
val = _val;
next = _next;
}
};
*/
class Solution {
public Node insert(Node head, int insertVal) {
// 判空
if(head == null) {
Node node = new Node(insertVal);
node.next = node;
return node;
}
// 寻找极大值、极小值
Node max = head;
Node min = head;
Node cur = head.next; // 指针
while(cur != head) {
if(cur.val >= max.val) max = cur;
if(cur.val <= min.val) min = cur;
cur = cur.next;
}
// 分类讨论
if(insertVal >= max.val || insertVal <= min.val) {
// 最小的前面 == 最大的后面（循环链表）
Node temp = new Node(insertVal, max.next);
max.next = temp;
}else {
// 找到次小于insertVal的节点
while(min.next.val < insertVal) min = min.next;
Node temp = new Node(insertVal, min.next);
min.next = temp;
}
return head;
}
}四、环形链表
1.1 快慢指针
题：剑指 Offer II 022. 链表中环的入口节点
解：
解题思路：
- 设v1，v2，s1，s2分别表示slow，fast的速度、路程，易得：
v2 = 2v1，s2 = 2s1，a，b见图 - 若相遇：fast 比 slow 多走了几个环
s2 = s1 + nb = 2s1 => s1 = nb - 待求点的位置：a + nb = s1 + a => slow继续走a步
- a步： 双指针同步从head，fast、slow相遇点出发，相遇点即为待求点
AC代码：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
// 快慢指针
ListNode fast = head, slow = head;
// 相遇点
while(true) {
// 指针走到了链表末端
if(fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) break;
}
fast = head;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}- 时间复杂度：O（N）
- 空间复杂度：O（1），双指针使用常数空间
题：142. 环形链表 II
题：面试题 02.08. 环路检测
题：141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
解：
解题思路：同上
AC代码：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
ListNode slow = head, fast = head;
while(true) {
if(fast.next == null || fast.next.next == null) return false;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
}
}- 时间复杂度：O（N）
- 空间复杂度：O（1）
