链表 UNLOCK

单向链表的反转

2019.08.26 17:57 0

单向链表的反转很考验逻辑思维,在面试中经常会被用到,因此是一个必须掌握的知识点。单向链表的反转有很多方法可以处理,这里介绍两种方法:遍历反转法递归反转法

单向链表结构

首先定义结构

1
2
3
4
5
6
7
8
9
10
public class ListNode {
//结点的val
int val;
//下一个结点
ListNode next;

ListNode(int x) {
val = x;
}
}

问题描述

将单链表数据:1, 2, 3, 4, 5 反转为:5, 4, 3, 2, 1

遍历反转法

  • 从前往后反转各个结点的指针域的指向。

  • 将当前结点curNode的下一个结点 curNode.next 缓存到 temp 后,然后,使当前结点指针指向上一结点 pre

  • 也就是说在反转当前结点指针指向前,先把当前结点的指针域用 tmp 临时保存,以便下一次使用,代码如下:

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
/**
* 遍历反转法:从前往后反转各个结点的指针域的指向。
* @param head
* @return preNode
*/
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
// 上一结点
ListNode preNode = head;
// 当前结点
ListNode curNode = head.next;
// 临时结点,用于保存当前结点的指针域(即下一结点)
ListNode tmp;
while (curNode != null) {
tmp = curNode.next;
// 反转指向
curNode.next = preNode;
// 向下移动
preNode= curNode;
curNode = tmp;
}
head.next = null;
return preNode;
}

递归反转法

  • 在反转当前结点之前先反转后续结点。这样从头结点开始,层层深入直到尾结点才开始反转指针域的指向。

  • 就是从尾结点开始,逆向反转各个结点的指针域指向。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 递归反转法:从尾结点开始,逆向反转各个结点的指针域指向。
* @param head
* @return reverseHead
*/
public ListNode reverseListRecur(ListNode head) {
// head看作是前一结点,head.next 是当前结点,reverseHead是反转后新链表的头结点
// 若为空链或者当前结点在尾结点,则直接还回
if (head == null || head.next == null) {
return head;
}
// 先反转后续结点 head.next
ListNode reverseHead = reverseListRecur(head.next);
// 将当前结点的指针域指向前一结点
head.next.next = head;
// 前一结点的指针域设为null;
head.next = null;
// 反转后新链表的头结点
return reverseHead;
}

代码看起来很简单,实际理解起来却十分烧脑,因此建议你自己在编译器上写一写,打断点去深入理解下。

评论加载中