-
Notifications
You must be signed in to change notification settings - Fork 0
/
SingleLinkedList.java
157 lines (130 loc) · 3.33 KB
/
SingleLinkedList.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
148
149
150
151
152
153
154
155
156
157
package com.fantasy.datastructure.linkedlist;
/**
* 单链表
*
* <pre>
* author : Fantasy
* version : 1.1, 2020-07-03
* since : 1.0, 2020-07-02
* </pre>
*/
public class SingleLinkedList {
private ListNode head;
public SingleLinkedList() {
head = null;
}
public void insertHead(int value) {
insertHead(new ListNode(value));
}
public void insertHead(ListNode node) {
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
}
public void insertTail(int value) {
insertTail(new ListNode(value));
}
public void insertTail(ListNode node) {
if (head == null) {
head = node;
} else {
ListNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}
public void insertAfter(ListNode node, int value) {
insertAfter(node, new ListNode(value));
}
public void insertAfter(ListNode node, ListNode newNode) {
if (node == null) {
return;
}
newNode.next = node.next;
node.next = newNode;
}
public void insertBefore(ListNode node, int value) {
insertBefore(node, new ListNode(value));
}
public void insertBefore(ListNode node, ListNode newNode) {
if (node == null) {
return;
}
if (node == head) {
insertHead(newNode);
}
ListNode temp = head;
while (temp != null && temp.next != node) {
temp = temp.next;
}
if (temp == null) {
return;
}
newNode.next = node;
temp.next = newNode;
}
public void delete(ListNode node) {
if (node == null || head == null) {
return;
}
if (node == head) {
head = head.next;
return;
}
ListNode temp = head;
while (temp != null && temp.next != node) {
temp = temp.next;
}
if (temp == null) {
return;
}
temp.next = temp.next.next;
}
public void deleteFirst(int value) {
if (head == null) {
return;
}
if (value == head.val) {
head = head.next;
return;
}
ListNode temp = head;
while (temp.next != null && temp.next.val != value) {
temp = temp.next;
}
if (temp.next == null) {
return;
}
temp.next = temp.next.next;
}
public void deleteAll(int value) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode temp = dummy;
while (temp.next != null) {
if (temp.next.val == value) {
temp.next = temp.next.next;
continue;
}
temp = temp.next;
}
head = dummy.next;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (ListNode node = head; node != null; node = node.next) {
sb.append(node.val);
if (node.next != null) {
sb.append(",").append(" ");
}
}
sb.append("]");
return sb.toString();
}
}