/
MainAlgorithm.java
119 lines (113 loc) · 3 KB
/
MainAlgorithm.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
118
119
package E链表.A004翻转一个链表;
import java.util.ArrayList;
import java.util.List;
import E链表.A001实现一个链表.ListNode;
import E链表.A001实现一个链表.MyListLink;
/**
* Description: <翻转一个链表><br>
* Author: mxdl<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
MyListLink link = new MyListLink();
link.addLast(0);
link.addLast(1);
link.addLast(2);
link.addLast(3);
/* ListNode listNote = reverseListNode(link.getListLink());
while (listNote != null) {
System.out.println(listNote.getData());
listNote = listNote.next;
}*/
/* System.out.println(link.getListLink());
System.out.println(reverseListNode3(link.getListLink()));*/
System.out.println(reverse(null,link.getListLink()));
}
//最简单的指针法
private static ListNode reverseListNode3(ListNode head){
ListNode prev = null;
ListNode curr = head;
while(curr != null){
//断开
ListNode next = curr.next;
//翻转
curr.next = prev;
//指针滑动prev
prev = curr;
//指针滑动curr
curr = next;
}
return prev;
}
//递归法,时间复杂度和空间复杂度都是O(n)
private static ListNode reverse(ListNode prev,ListNode curr){
if(curr == null){
return prev;
}
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
return reverse(prev,curr);
}
// 指针法
private static ListNode reverseListNode2(ListNode listNote) {
// 声明的头指针
ListNode head = listNote;
// 申明一个尾指针
ListNode tail = listNote;
// 声明一个next指针
ListNode next = listNote.next;
// 计算链表的长度
int size = 0;
ListNode temp = listNote;
while (temp != null) {
size++;
temp = temp.next;
}
while (size > 1) {
// 缓存一个next
ListNode nextNext = next.next;
// 更改next的next指针
next.next = head;// 反向了
// 移动head指针的指向
head = next;
// 移动next指针的指向
next = nextNext;
size--;
}
// 此时链表有环,干掉环
tail.next = null;
return head;
}
// 数组法
private static ListNode reverseListNode(ListNode listNote) {
// 翻转一个链表
ListNode tempNode = listNote;
// 把链表的值都放入List集合里面
// 通过翻转数组来翻转集合
List<ListNode> list = new ArrayList<>();
while (tempNode != null) {
list.add(tempNode);
tempNode = tempNode.next;
}
ListNode headNode = null;
for (int i = list.size() - 1; i >= 0; i--) {
if (headNode == null) {
headNode = new ListNode();
headNode = list.get(i);
headNode.next = list.get(i - 1);
} else {
if (i == 0) {
list.get(i).next = null;
} else {
list.get(i).next = list.get(i - 1);
}
}
}
return headNode;
}
}