给定一个单链表 list ,请将它反转后返回,示例:
原链表:
反转链表:
定义的单链表结点类结构如下:
public class ListNode {
public Integer value;
public ListNode next;
public ListNode() {
}
public ListNode(int value) {
this.value = value;
}
}
我们先写两个方法,用于组装成链表和将链表打印到控制台,方便进行算法结果验证:
public ListNode assemble(int[] items) {
if (items == null || items.length == 0) {
return null;
}
ListNode list = new ListNode(items[0]);
ListNode node = list;
for (int i = 1; i < items.length; i++) {
node.next = new ListNode(items[i]);
node = node.next;
}
return list;
}
public void print(ListNode list) {
if (list == null) {
System.out.print("<空>");
}
while (list != null) {
System.out.print(list.value + " -> ");
list = list.next;
}
System.out.println("null");
}
1. “栈”反转
“栈”是一种先进后出 (FILO) 的数据结构,我们可以利用它的这个特性来实现反转链表。
1)先将链表结点顺序入栈:
2)然后开始将结点出栈,并逐一反转指针指向:
为了能在最后返回反转链表,我们给栈顶结点使用一个top 结点引用来指向它,通过top 结点,能够在完成反转链表后,按顺序访问到完整的反转链表的所有结点;此外,为了在出栈的时候,能反转指针指向,另外定义多两个结点prev 和rear ,初始prev 和top 指向同一个结点栈顶结点,即反转链表的首结点。
- 将结点
4 出栈(rear 结点),并反转指针指向4 -> 5 为5 -> 4 ,此时结点4 指向NULL ,即不指向任何一个实结点:
prev 结点往后顺移一个结点位置,此时指向结点4 ,并将结点3 出栈(rear 结点),然后反转指针指向3 -> 4 为4 -> 3 :
prev 结点往后顺移一个结点位置,此时指向结点3 ,并将结点2 出栈(rear 结点),然后反转指针指向2 -> 3 为3 -> 2 :
prev 结点往后顺移一个结点位置,此时指向结点2 ,并将结点1 出栈(rear 结点),然后反转指针指向1 -> 2 为2 -> 1 :
3)代码实现:
public ListNode reverseByStack(ListNode list) {
if (list == null || list.next == null) {
return list;
}
Deque<ListNode> stack = new LinkedList<>();
while (list != null) {
stack.push(list);
list = list.next;
}
ListNode top = stack.pop();
ListNode prev = top, rear;
while (!stack.isEmpty()) {
rear = stack.pop();
prev.next = rear;
rear.next = null;
prev = rear;
}
return top;
}
4)结果验证:
int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表:");
print(list);
ListNode rlist = reverseByStack(list);
System.out.print("反转单链表:");
print(rlist);
原始单链表:16 -> 24 -> 48 -> 43 -> 4 -> 9 -> 47 -> 42 -> null
反转单链表:42 -> 47 -> 9 -> 4 -> 43 -> 48 -> 24 -> 16 -> null
2. 递归法
将原链表的结点按顺序一直递归到最后一层,也就是原链表的尾结点,将尾结点引用透传返回至递归方法第一层,在每一层里,将结点指针指向逆转,然后方法返回。注意:当链表长度太长时,这种方式会抛出 java.lang.StackOverflowError 。
1)将原链表的结点按顺序一直递归到最后一层,将尾结点5 返回:
2)尾结点5 透传返回,并在每一层中,反转指针指向:
尾结点5 使用rlist 引用指向它,注意在反转指针指向的时候,不能使用rlist 引用来操作,因为在每一层递归中,rlist 都要保证是往上“透传”的,也就是说它永远是5 结点。
- 反转指针指向
4 -> 5 为5 -> 4 ,此时结点4 指向NULL ,即不指向任何一个实结点:
3)代码实现:
public ListNode reverseRecursively(ListNode list) {
if (list == null || list.next == null) {
return list;
}
ListNode rlist = reverseRecursively(list.next);
list.next.next = list;
list.next = null;
return rlist;
}
4)结果验证:
int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表:");
print(list);
ListNode rlist = reverseRecursively(list);
System.out.print("反转单链表:");
print(rlist);
原始单链表:44 -> 28 -> 3 -> 11 -> 49 -> 3 -> 20 -> 13 -> null
反转单链表:13 -> 20 -> 3 -> 49 -> 11 -> 3 -> 28 -> 44 -> null
3. 就地逆置(单指针法)
这种方法比较好理解,就是将链表的所有结点按顺序迭代,并且在每一次迭代时,调整指针指向。需要增加两个指针引用prev 和rear ,分别用于定位当前链表结点的前一个结点和后一个结点,以方便进行指针指向调整操作。
1)定义prev 和rear 结点引用,按顺序迭代链表结点:
- 初始化
prev 指向NULL ,rear 未指向任何结点:
rear 指向2 结点(当前结点list 的下一结点),调整指针指向1 -> 2 为1 -> NULL ,并将prev 和list 往后顺移一个结点位置(此时prev 指向1 ,list 指向2 ):
rear 指向3 结点(当前结点list 的下一结点),调整指针指向2 -> 3 为2 -> 1 ,并将prev 和list 往后顺移一个结点位置(此时prev 指向2 ,list 指向3 ):
rear 指向4 结点(当前结点list 的下一结点),调整指针指向3 -> 4 为3 -> 2 ,并将prev 和list 往后顺移一个结点位置(此时prev 指向3 ,list 指向4 ):
rear 指向5 结点(当前结点list 的下一结点),调整指针指向4 -> 5 为4 -> 3 ,并将prev 和list 往后顺移一个结点位置(此时prev 指向4 ,list 指向5 ):
rear 指向NULL 结点(当前结点list 的下一结点),调整指针指向5 -> NULL 为5 -> 4 ,并将prev 和list 往后顺移一个结点位置(此时prev 指向5 ,list 指向NULL ):
2)代码实现:
public ListNode reverseInSitu1(ListNode list) {
if (list == null || list.next == null) {
return list;
}
ListNode prev = null, rear;
while (list != null) {
rear = list.next;
list.next = prev;
prev = list;
list = rear;
}
return prev;
}
3)结果验证:
int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表:");
print(list);
ListNode rlist = reverseInSitu1(list);
System.out.print("反转单链表:");
print(rlist);
原始单链表:11 -> 12 -> 2 -> 15 -> 17 -> 38 -> 10 -> 1 -> null
反转单链表:1 -> 10 -> 38 -> 17 -> 15 -> 2 -> 12 -> 11 -> null
4. 就地逆置(双指针法)
这种方法跟上一种方法比较类似,不同的是,当前结点list 在每一次迭代时,并不会往后顺移一个结点位置,而是指向rear 结点(当前结点list 的下下一结点),此方法比“单指针法”少一次迭代。需要增加两个指针引用prev 和rear ,分别用于定位当前链表结点的前结点(初始等于当前结点)和后结点,以方便进行指针指向调整操作。
1)定义prev 和rear 结点引用,按顺序迭代链表结点:
- 初始化
prev 指向1 (和list 指向同一个结点),rear 未指向任何结点:
rear 指向3 结点(当前结点list 的下下一结点),调整指针指向2 -> 3 为2 -> 1 ,将prev 往后顺移一个结点位置(此时prev 指向2 ),然后将list 指针指向3 (即1 -> 2 调整为1 -> 3 ,打破上一个指针指向调整形成的1 -> 2 -> 1 的“环”):
rear 指向4 结点(当前结点list 的下下一结点),调整指针指向3 -> 4 为3 -> 2 ,将prev 往后顺移一个结点位置(此时prev 指向3 ),然后将list 指针指向4 (即1 -> 3 调整为1 -> 4 ,打破上一个指针指向调整形成的1 -> 3 -> 2 -> 1 的“环”):
rear 指向5 结点(当前结点list 的下下一结点),调整指针指向4 -> 5 为4 -> 3 ,将prev 往后顺移一个结点位置(此时prev 指向4 ),然后将list 指针指向5 (即1 -> 4 调整为1 -> 5 ,打破上一个指针指向调整形成的1 -> 4 -> 3 -> 2 -> 1 的“环”):
rear 指向NULL 结点(当前结点list 的下下一结点),调整指针指向5 -> NULL 为5 -> 4 ,将prev 往后顺移一个结点位置(此时prev 指向5 ),然后将list 指针指向NULL (即1 -> 5 调整为1 -> NULL ,打破上一个指针指向调整形成的1 -> 5 -> 4 -> 3 -> 2 -> 1 的“环”):
可以看到,“双指针法”的第一个指针用于反转指针指向,但这会形成一个“环”,而第二个指针就是为了打破这个环,同时指向下一个操作的结点(rear 结点引用就是为了保存它,以便在每次迭代的最后一步中list 可以找到并指向它)。
2)代码实现:
public ListNode reverseInSitu2(ListNode list) {
if (list == null || list.next == null) {
return list;
}
ListNode prev = list, rear;
while (list.next != null) {
rear = list.next.next;
list.next.next = prev;
prev = list.next;
list.next = rear;
}
return prev;
}
3)结果验证:
int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表:");
print(list);
ListNode rlist = reverseInSitu2(list);
System.out.print("反转单链表:");
print(rlist);
原始单链表:25 -> 38 -> 50 -> 47 -> 16 -> 30 -> 27 -> 40 -> null
反转单链表:40 -> 27 -> 30 -> 16 -> 47 -> 50 -> 38 -> 25 -> null
5. 头插法
头插法是在每次插入新元素时,插入到一个被称为“头结点”的元素的后面的方法,在 JDK 7 的 java.util.HashMap 类中也有应用。
1)定义一个临时“头结点”tmpHead ,rear 结点引用,按顺序迭代链表结点,并将它们插入到tmpHead 的后面:
- 初始化临时头结点
tmpHead ,rear 结点引用未指向任何结点:
rear 指向2 结点(当前结点list 的下一结点),将结点1 插入到tmpHead 后面(结点NULL 前面),将当前结点list 往后顺移一个结点位置(此时list 指向2 ):
rear 指向3 结点(当前结点list 的下一结点),将结点2 插入到tmpHead 后面(结点1 前面),将当前结点list 往后顺移一个结点位置(此时list 指向3 ):
rear 指向4 结点(当前结点list 的下一结点),将结点3 插入到tmpHead 后面(结点2 前面),将当前结点list 往后顺移一个结点位置(此时list 指向4 ):
rear 指向5 结点(当前结点list 的下一结点),将结点4 插入到tmpHead 后面(结点3 前面),将当前结点list 往后顺移一个结点位置(此时list 指向5 ):
rear 指向NULL 结点(当前结点list 的下一结点),将结点5 插入到tmpHead 后面(结点4 前面),将当前结点list 往后顺移一个结点位置(此时list 指向NULL ):
2)代码实现:
public ListNode reverseByHeadInsertion(ListNode list) {
if (list == null || list.next == null) {
return list;
}
ListNode tmpHead = new ListNode(), rear;
while (list != null) {
rear = list.next;
list.next = tmpHead.next;
tmpHead.next = list;
list = rear;
}
return tmpHead.next;
}
3)结果验证:
int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表:");
print(list);
ListNode rlist = reverseByHeadInsertion(list);
System.out.print("反转单链表:");
print(rlist);
原始单链表:6 -> 24 -> 39 -> 7 -> 27 -> 37 -> 22 -> 36 -> null
反转单链表:36 -> 22 -> 37 -> 27 -> 7 -> 39 -> 24 -> 6 -> null
3)结果验证:
int[] items = IntStream.generate(() -> 1 + (int) (Math.random() * 50)).limit(8).toArray();
ListNode list = assemble(items);
System.out.print("原始单链表:");
print(list);
ListNode rlist = reverseByHeadInsertion(list);
System.out.print("反转单链表:");
print(rlist);
原始单链表:6 -> 24 -> 39 -> 7 -> 27 -> 37 -> 22 -> 36 -> null
反转单链表:36 -> 22 -> 37 -> 27 -> 7 -> 39 -> 24 -> 6 -> null
|