主要內(nèi)容：
- 單鏈表的基本操作
- 刪除重復(fù)數(shù)據(jù)
- 找到倒數(shù)第k個(gè)元素
- 實(shí)現(xiàn)鏈表的反轉(zhuǎn)
- 從尾到頭輸出鏈表
- 找到中間節(jié)點(diǎn)
- 檢測鏈表是否有環(huán)
- 在不知道頭指針的情況下刪除指定節(jié)點(diǎn)
- 如何判斷兩個(gè)鏈表是否相交并找出相交節(jié)點(diǎn)
直接上代碼，就是這么奔放~~~
|
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 * 實(shí)現(xiàn)單鏈表的基本操作,增加刪除節(jié)點(diǎn)、排序、打印、計(jì)算長度 */public class MyLinkedList { Node head = null;//鏈表頭的作用 /**向鏈表中插入數(shù)據(jù) * @param d：插入數(shù)據(jù)的內(nèi)容 */ 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個(gè)節(jié)點(diǎn) * @return 成功返回true，失敗返回false */ public Boolean deleteNode(int index){ if(index<1||index>length()){ return false;//刪除元素位置不合理 } //刪除鏈表中的第一個(gè)元素 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; } /** * 對鏈表進(jìn)行排序 * @return 返回排序后的頭結(jié)點(diǎn) */ 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; } /** * 打印鏈表中所有數(shù)據(jù) */ public void printList(){ Node tmp=head; while(tmp!=null){ System.out.print(tmp.data+" "); tmp=tmp.next; } System.out.println(); } /** * 從鏈表中刪除數(shù)據(jù)的第一種方法 * 遍歷鏈表，把遍歷到的數(shù)據(jù)存到一個(gè)Hashtable中，在遍歷過程中若當(dāng)前訪問的值在Hashtable * 中存在，則可以刪除 * 優(yōu)點(diǎn)：時(shí)間復(fù)雜度低 缺點(diǎn)：需要額外的存儲(chǔ)空間來保存已訪問過得數(shù)據(jù) */ 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; } } /** * 從鏈表中刪除重復(fù)數(shù)據(jù)的第二種方法 * 雙重循環(huán)遍歷 * 優(yōu)缺點(diǎn)很明顯 */ 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：找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn) * @return 該節(jié)點(diǎn) * 設(shè)置兩個(gè)指針p1、p2，讓p2比p1快k個(gè)節(jié)點(diǎn)，同時(shí)向后遍歷，當(dāng)p2為空，則p1為倒數(shù)第k個(gè)節(jié)點(diǎn) */ 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; } /** * 實(shí)現(xiàn)鏈表的反轉(zhuǎn) * @param head鏈表的頭節(jié)點(diǎn) */ 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+" "); } } /** * 查詢單鏈表的中間節(jié)點(diǎn) * 定義兩個(gè)指針，一個(gè)每次走一步，一個(gè)每次走兩步... * @param head * @return q為中間節(jié)點(diǎn) */ 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; } /** * 在不知道頭指針的情況下刪除指定節(jié)點(diǎn) * 鏈表尾節(jié)點(diǎn)無法刪除，因?yàn)閯h除后無法使其前驅(qū)節(jié)點(diǎn)的next指針置為空 * 其他節(jié)點(diǎn)，可以通過交換這個(gè)節(jié)點(diǎn)與其后繼節(jié)點(diǎn)的值，然后刪除后繼節(jié)點(diǎn) * @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; } /** * 判斷兩個(gè)鏈表是否相交 * 如果兩個(gè)鏈表相交，則肯定有相同的尾節(jié)點(diǎn)，遍歷兩個(gè)鏈表，記錄尾節(jié)點(diǎn)，看是否相同 * @param h1鏈表1的頭節(jié)點(diǎn) * @param h2鏈表2的頭結(jié)點(diǎn) * @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; } /** * 找出相交的第一個(gè)節(jié)點(diǎn) * @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(); }} |
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時(shí)也希望多多支持服務(wù)器之家！
原文鏈接：http://www.cnblogs.com/winorgohome/p/6028309.html
