概览：
1）按值传递、按引用传递 （我不知道为什么如此多的同学会犯这种错误，这完全是语言问题）
2）单链表、双链表的定义
3）根据反转功能，彻底从系统角度解释链表是如何调整的
链表题目在笔试、面试中的意义就是检验coding能力如何
更难的题目会在【必备】课程里讲述
1 按值传递、按引用传递
左老师讲了Java中的按值传递、按引用传递。结合我个人的一些理解，我将其书面的表达总结了。参考博客：java只有按值传递
2 单链表和双链表的定义
单链表维持val和next
双链表维持val,next和pre
3 力扣206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
1
2
输入：head = [1,2]
输出：[2,1]
示例 3：
1
2
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解法：遍历一次
拿3个指针(cur,pre,next)搞一搞就行：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 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 reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode cur = head, pre = null, next;
while (cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
时间复杂度O(n),空间复杂度O(1)
解法：递归版
解法：迭代版
力扣92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
1
2
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
1
2
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
解法：遍历一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* 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) {
if (head == null || head.next == null || left == right) return head;
ListNode cur = head, pre = null, next, partOneTail, partTwoTail;
int k = 1;
while (k < left) {
pre = cur;
cur = cur.next;
k++;
}
partOneTail = pre;
partTwoTail = cur;
pre = cur;
cur = cur.next;
while (k < right) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
k++;
}
if (partOneTail == null) {
head = pre;
}else {
partOneTail.next = pre;
}
partTwoTail.next = cur;
return head;
}
}
总结下思路：
- 定位反转区间的起点和前驱：
- 使用指针 cur 和 pre，遍历到第 left 个节点。
- pre 停在第 left-1 个节点（可能是 null，如果 left=1），cur 指向第 left 个节点。
- 记录 partOneTail = pre（第一部分的尾节点）。
- 标记反转区间的起点：
- partTwoTail = cur，即反转部分的原始起点（第 left 个节点），后续用来连接第三部分。
- 反转第 left 到 right 的部分：
- 使用经典链表反转方法（prev, curr, next 指针法，也就是力扣206题的思路）。
- 从第 left 到第 right 个节点，逐个调整 next 指针，使其指向前一个节点。
- 反转后，pre 指向第 right 个节点（新头部），cur 指向第 right+1 个节点。
- 连接三部分：
- 如果 partOneTail 是 null（即 left=1），新头节点是反转后的 pre。
- 否则，partOneTail.next = pre，连接第一部分和反转后的第二部分。
- partTwoTail.next = cur，连接反转后的第二部分和第三部分。
- 返回结果：
- 返回 head（可能是原始头或新头）。
这个思路还是比较丝滑的，其中需要考虑partOneTail是不是空的问题（当left=1的时候就需要这么考虑）
反转双链表
1
2
3
4
5
6
7
8
9
10
11
public DoubleListNode reverse(DoubleListNode head) {
DoubleListNode pre = null, next;
while (head != null) {
next = head.next;
head.next = pre;
head.pre = next;
pre = head;
head = next;
}
return pre;
}
