单向链表逆序
约 438 字
预计阅读 1 分钟
次阅读
要求:在一个原有的单链表上执行逆序操作
处理思路
- 定义一个反转节点
- 遍历原链表,每遍历一个节点都将该节点指向反转节点的第一个元素,跟"头插法"一样
- 将原链表的头节点指向反转节点的第一个元素。
下面这张图可以很好地说明这个过程

代码实现
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
|
public void reverse() {
// 如果没有元素或只有一个元素无需反转
if (head.next == null || head.next.next == null) {
System.out.println("无需反转");
return;
}
// 定义一个反转节点
Node reverse = new Node();
// 定义一个当前变量,用来遍历
Node cur = head.next;
// 定义next节点变量用来保存当前节点的下一个节点
Node next;
while (cur != null) {
// 1. 保存当前节点的下一个节点
next = cur.next;
// 2. 将当前节点指向反转节点的第一个元素
cur.next = reverse.next;
// 3. 将反转节点指向当前节点
reverse.next = cur;
// 4. 遍历下一个节点
cur = next;
}
head.next = reverse.next;
}
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.reverse();
System.out.println("========反转后的链表========");
list.display();
}
|
运行结果
