反转单链表和双链表。
题目
206. 反转链表 - 力扣（LeetCode）
https://leetcode.com/problems/reverse-linked-list
题目难度：Easy
解答1[Java]：迭代法/遍历法
核心思想
遍历一遍链表，遍历到下一个元素的时候，保留上一个元素的引用，这样就可以直接把当前元素的 next 设置为上一个元素。
每次遍历时候，先把下个节点临时保存下，然后把当前节点的 next 设置为 prev，然后再之前临时保存的下一个元素进行下一次遍历。
由于每次遍历的时候，都会使用下一个元素，当下一个元素变为 null 的时候，也就意味着遍历结束。
代码
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
|
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}
|
解答2[Java]：递归法
核心思想
先递归到最后一个节点，然后返回最后一个节点的指针。最后一个节点的指针一直传回递归的最顶层，同时每次递归返回之前，翻转当前节点和自己的下一个节点的关系。最后返回的指针是最后一个节点的指针，同时相邻节点的关系都被翻转了。
主要是利用 head.next.next = head; 相当于翻转了当前节点和下一个节点的关系。递归调用到最后，p 一直是指向最后一个节点，并且不断被返回到上一层调用的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}
|
拓展：反转双向链表
核心思路
代码
双向链表节点定义
1
2
3
4
5
6
7
8
9
| public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
|
算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public static DoubleNode reverseList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode post = null;
while (head != null) {
post = head.next;
head.next = pre;
head.last = post;
pre = head;
head = post;
}
return pre;
}
}
|
完整测试代码
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| public class Code_07_ReverseList {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node reverseList(Node head) {
Node pre = null;
Node post = null;
while (head != null) {
post = head.next;
head.next = pre;
pre = head;
head = post;
}
return pre;
}
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
public static DoubleNode reverseList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode post = null;
while (head != null) {
post = head.next;
head.next = pre;
head.last = post;
pre = head;
head = post;
}
return pre;
}
public static void printLinkedList(Node head) {
System.out.print("Linked List: ");
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
System.out.println();
}
public static void printDoubleLinkedList(DoubleNode head) {
System.out.print("Double Linked List: ");
DoubleNode end = null;
while (head != null) {
System.out.print(head.value + " ");
end = head;
head = head.next;
}
System.out.print("| ");
while (end != null) {
System.out.print(end.value + " ");
end = end.last;
}
System.out.println();
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
printLinkedList(head1);
head1 = reverseList(head1);
printLinkedList(head1);
DoubleNode head2 = new DoubleNode(1);
head2.next = new DoubleNode(2);
head2.next.last = head2;
head2.next.next = new DoubleNode(3);
head2.next.next.last = head2.next;
head2.next.next.next = new DoubleNode(4);
head2.next.next.next.last = head2.next.next;
printDoubleLinkedList(head2);
printDoubleLinkedList(reverseList(head2));
}
}
|
相关题目
92. 反转链表 II - 力扣（LeetCode）
实际考察
CodeTop 上的信息
字节跳动：迭代法和递归都需要写出来
反转链表二也做一下，美团3.31面试题
字节火山面试题，写出来后让分析有环的链表运行结果，关键点：1.是否会死循环（不会） 2.返回结果（环内翻转，环外未翻转）
补充题：反转双向链表
百度一面，反转双向链表
小米二面
8.20广州多益网络手撕出现了
参考资料