-
Notifications
You must be signed in to change notification settings - Fork 0
/
ReverseList.java
119 lines (101 loc) · 2.4 KB
/
ReverseList.java
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package com;
/**
* 剑指offer: 链表反转
* 两种方法求解:1.遍历;2.递归.
* 测试用例三种(链表有多个节点,一个节点核链表为空)
* @author dingding
* Date:2017-6-14 9:55
* Declaration: All Rights Reserved!
*/
public class ReverseList {
public static void main(String[] args) {
test1();
test2();
test3();
}
private static class ListNode{
int value;
ListNode next;
}
//遍历的方式进行反转,返回反转后的头结点(pReversedHead)
private static ListNode reverseListIteratively(ListNode pHead){
ListNode pReversedHead = null;
ListNode pNode = pHead;
ListNode pPrev = null;
while(pNode!=null){
ListNode pNext = pNode.next;
if (pNext==null) {
pReversedHead = pNode;
}
pNode.next = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
//递归方法进行反转,返回下一个递归的节点
private static ListNode reverseListRecursively(ListNode pHead){
if (pHead==null) {
//System.out.println("链表为空!");
return null;
}else {
while (pHead!=null && pHead.next==null){
return pHead;
}
ListNode pNode = reverseListRecursively(pHead.next);
pHead.next.next=pHead;
pHead.next=null;
return pNode;
}
}
private static void printList(ListNode pHead){
if (pHead==null) {
System.out.println("链表为空!");
}else {
while(pHead!=null){
System.out.print(pHead.value+" ");
pHead = pHead.next;
}
}
System.out.println();
}
/*================测试代码================================ */
private static void test(ListNode first){
System.out.println("初始列表:");
printList(first);
System.out.println("遍历方法反转结果:");
ListNode pTail = reverseListIteratively(first);
printList(pTail);
System.out.println("递归方法反转结果:");
ListNode pNode = reverseListRecursively(pTail);
printList(pNode);
}
//输入的链表有多个节点
private static void test1(){
ListNode first = new ListNode();
ListNode second = new ListNode();
ListNode third = new ListNode();
ListNode fourth = new ListNode();
ListNode fifth = new ListNode();
first.value = 1;
second.value = 2;
third.value = 3;
fourth.value = 4;
fifth.value = 5;
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
test(first);
}
//输入的链表只有一个结点
private static void test2(){
ListNode first = new ListNode();
first.value=1;
test(first);
}
//输入空链表
private static void test3(){
test(null);
}
}