-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedList.java
147 lines (131 loc) · 3.51 KB
/
LinkedList.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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
class LinkedList {
public class ListNode{
public ListNode next = null;
public int val = -1;
public ListNode(int i){
val = i;
}
}
public boolean hasCycle(ListNode node){
if (node == null){
return false;
}
ListNode h = new ListNode(-1);
h.next = node;
ListNode ptr1 = h;
ListNode ptr2 = h;
while (ptr1 != null && ptr2 != null && ptr2.next != null){
if (ptr1 != h && ptr1 == ptr2){
break;
}
ptr1 = ptr1.next;
ptr2 = ptr2.next.next;
}
if (ptr2 == null || (ptr2 != null && ptr2.next == null)){
return false;
}else {
return true;
}
}
public ListNode nodeCycle(ListNode node){
if(node == null){
return null;
}
ListNode h = new ListNode(-1);
h.next = node;
ListNode ptr1 = h;
ListNode ptr2 = h;
while (ptr1 != null && ptr2 != null && ptr2.next != null){
if (ptr1 != h && ptr1 == ptr2){
break;
}
ptr1 = ptr1.next;
ptr2 = ptr2.next.next;
}
if (ptr2 == null || (ptr2 != null && ptr2.next == null)){
return null;
}else {
int count = 1;
ptr2 = ptr1.next;
while (ptr2 != ptr1){
ptr2 = ptr2.next;
count++;
}
ptr1 = h;
ptr2 = h;
while (count>=0){
ptr2 = ptr2.next;
count--;
}
while (ptr1 != ptr2){
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return ptr1;
}
}
public ListNode search(ListNode node, int target){
ListNode h = new ListNode(-1);
h.next = node;
ListNode ptr = h;
while (ptr != null){
if (ptr.val == target){
return ptr;
}
}
return null;
}
public boolean remove(ListNode node, ListNode pre, int target){
if (node == null){
return null;
}else {
if (node.val == target){
pre.next = node.next;
return true;
}
return remove(node.next,node,target);
}
}
public boolean insert(ListNode node, ListNode n, int target){
while (node != null && target != node.val){
node = node.next;
}
if (node == null){
return false;
}else {
n.next = node.next;
node.next = n;
return true;
}
}
public ListNode reverse(ListNode node, ListNode pre){
if (node != null){
ListNode tmp = node.next;
node.next = pre;
return reverse(tmp, node);
}else {
return pre;
}
}
public ListNode append(ListNode ptr1, ListNode ptr2){
if (ptr1 == null){
return ptr2;
}else {
ptr1.next = append(ptr1.next,ptr2);
return ptr1;
}
}
public ListNode merge(ListNode ptr1, ListNode ptr2){
if (ptr1 == null){
return ptr2;
}else if (ptr2 == null){
return ptr1;
}else if (ptr1.val < ptr2.val){
ptr1.next = merge(ptr1.next, ptr2);
return ptr1;
}else {
ptr2.next = merge(ptr1,ptr2.next);
return ptr2;
}
}
}