主要內容：
- 單鏈表的基本操作
- 刪除重復數據
- 找到倒數第k個元素
- 實現鏈表的反轉
- 從尾到頭輸出鏈表
- 找到中間節點
- 檢測鏈表是否有環
- 在不知道頭指針的情況下刪除指定節點
- 如何判斷兩個鏈表是否相交并找出相交節點
直接上代碼，就是這么奔放~~~
|
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
|
package pers.ty.$1101datastructure;import java.util.Hashtable;/** * @author Administrator * 實現單鏈表的基本操作,增加刪除節點、排序、打印、計算長度 */public class MyLinkedList { Node head = null;//鏈表頭的作用 /**向鏈表中插入數據 * @param d：插入數據的內容 */ public void addNode(int d){ Node newNode=new Node(d); if(head==null){ head=newNode; return; } Node tmp=head; while(tmp.next!=null){ tmp=tmp.next; } //add Node to end tmp.next=newNode; } /** * @param index:刪除第index個節點 * @return 成功返回true，失敗返回false */ public Boolean deleteNode(int index){ if(index<1||index>length()){ return false;//刪除元素位置不合理 } //刪除鏈表中的第一個元素 if(index==1){ head=head.next; return true; } int i=1; Node preNode=head; Node curNode=preNode.next; while(curNode!=null){ if(i==index){ preNode.next=curNode.next; return true; } preNode=curNode; curNode=curNode.next; i++; } return true; } /** * @return 返回鏈表的長度length */ public int length(){ int length=0; Node tmp=head; while(tmp!=null){ length++; tmp=tmp.next; } return length; } /** * 對鏈表進行排序 * @return 返回排序后的頭結點 */ public Node orderList(){ Node nextNode=null; int temp=0; Node curNode=head; while(curNode.next!=null){ nextNode=curNode.next; while(nextNode!=null){ if(curNode.data>nextNode.data){ temp=curNode.data; curNode.data=nextNode.data; nextNode.data=temp; } nextNode=nextNode.next; } curNode=curNode.next; } return head; } /** * 打印鏈表中所有數據 */ public void printList(){ Node tmp=head; while(tmp!=null){ System.out.print(tmp.data+" "); tmp=tmp.next; } System.out.println(); } /** * 從鏈表中刪除數據的第一種方法 * 遍歷鏈表，把遍歷到的數據存到一個Hashtable中，在遍歷過程中若當前訪問的值在Hashtable * 中存在，則可以刪除 * 優點：時間復雜度低 缺點：需要額外的存儲空間來保存已訪問過得數據 */ public void deleteDuplecate1(){ Hashtable<Integer,Integer> table=new Hashtable<Integer,Integer>(); Node tmp=head; Node pre=null; while (tmp!=null) { if(table.containsKey(tmp.data)) pre.next=tmp.next; else{ table.put(tmp.data, 1); pre=tmp; } tmp=tmp.next; } } /** * 從鏈表中刪除重復數據的第二種方法 * 雙重循環遍歷 * 優缺點很明顯 */ public void deleteDuplecate2(){ Node p=head; while (p!=null) { Node q=p; while(q.next!=null){ if(p.data==q.next.data){ q.next=q.next.next; }else{ q=q.next; } } p=p.next; } } /** * @param k：找到鏈表中倒數第k個節點 * @return 該節點 * 設置兩個指針p1、p2，讓p2比p1快k個節點，同時向后遍歷，當p2為空，則p1為倒數第k個節點 */ public Node findElem(Node head,int k){ if(k<1||k>this.length()) return null; Node p1=head; Node p2=head; for (int i = 0; i < k-1; i++) p2=p2.next; while (p2.next!=null) { p2=p2.next; p1=p1.next; } return p1; } /** * 實現鏈表的反轉 * @param head鏈表的頭節點 */ public void reverseIteratively(Node head){ Node pReversedHead=head; Node pNode=head; Node pPrev=null; while (pNode!=null) { Node pNext=pNode.next; if(pNext==null) pReversedHead=pNode; pNode.next=pPrev; pPrev=pNode; pNode=pNext; } this.head=pReversedHead; } /** * 通過遞歸從尾到頭輸出單鏈表 * @param head */ public void printListReversely(Node head){ if(head!=null){ printListReversely(head.next); System.out.print(head.data+" "); } } /** * 查詢單鏈表的中間節點 * 定義兩個指針，一個每次走一步，一個每次走兩步... * @param head * @return q為中間節點 */ public Node searchMid(Node head){ Node q=head; Node p=head; while (p!=null&&p.next!=null&&p.next.next!=null) { q=q.next; p=p.next.next; } return q; } /** * 在不知道頭指針的情況下刪除指定節點 * 鏈表尾節點無法刪除，因為刪除后無法使其前驅節點的next指針置為空 * 其他節點，可以通過交換這個節點與其后繼節點的值，然后刪除后繼節點 * @param n * @return */ public boolean deleteNode(Node n){ if(n==null||n.next==null) return false; int tmp=n.data; n.data=n.next.data; n.next.data=tmp; n.next=n.next.next; return true; } /** * 判斷兩個鏈表是否相交 * 如果兩個鏈表相交，則肯定有相同的尾節點，遍歷兩個鏈表，記錄尾節點，看是否相同 * @param h1鏈表1的頭節點 * @param h2鏈表2的頭結點 * @return 是否相交 */ public boolean isIntersect(Node h1,Node h2){ if(h1==null||h2==null) return false; Node tail1=h1; while (tail1.next!=null){ tail1=tail1.next; } Node tail2=h2; while(tail2.next!=null){ tail2=tail2.next; } return tail1==tail2; } /** * 找出相交的第一個節點 * @param h1 * @param h2 * @return */ public Node getFirstMeetNode(Node h1,Node h2){ if(h1==null||h2==null) return null; Node tail1=h1; int len1=1; while (tail1.next!=null){ tail1=tail1.next; len1++; } Node tail2=h2; int len2=1; while(tail2.next!=null){ tail2=tail2.next; len2++; } if(tail1!=tail2){ return null; } Node t1=h1; Node t2=h2; //找出較長的鏈表先遍歷 if(len1>len2){ int d=len1-len2; while(d!=0){ t1=t1.next; d--; } } if(len1<len2){ int d=len2-len1; while(d!=0){ t2=t2.next; d--; } } while(t1!=t2){ t1=t1.next; t2=t2.next; } return t1; } public static void main(String[] args) { MyLinkedList list=new MyLinkedList(); }} |
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://www.cnblogs.com/winorgohome/p/6028309.html
