forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ListNodeDemo.java
716 lines (603 loc) · 23.3 KB
/
ListNodeDemo.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
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
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
package Algorithms;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;
/**
* REFS:
* http://blog.csdn.net/fightforyourdream/article/details/16353519
* http://blog.csdn.net/luckyxiaoqiang/article/details/7393134 轻松搞定面试中的链表题目
* http://www.cnblogs.com/jax/archive/2009/12/11/1621504.html 算法大全(1)单链表
*
* 目录:
* 1. 求单链表中结点的个数: getListLength
* 2. 将单链表反转: reverseList(遍历),reverseListRec(递归)
* 3. 查找单链表中的倒数第K个节点(k > 0): reGetKthNode
* 4. 查找单链表的中间结点: getMiddleNode
* 5. 从尾到头打印单链表: reversePrintListStack,reversePrintListRec(递归)
* 6. 已知两个单链表pHead1 和pHead2 各自有序,把它们合并成一个链表依然有序: mergeSortedList, mergeSortedListRec
* 7. 判断一个单链表中是否有环: hasCycle
* 8. 判断两个单链表是否相交: isIntersect
* 9. 求两个单链表相交的第一个节点: getFirstCommonNode
* 10. 已知一个单链表中存在环,求进入环中的第一个节点: detectCycle, getFirstNodeInCycleHashMap
* 11. 给出一单链表头指针pHead和一节点指针pToBeDeleted,O(1)时间复杂度删除节点pToBeDeleted: delete
*
*/
public class ListNodeDemo {
// create the link Node class.
// why use static:
// http://duqiangcise.iteye.com/blog/697476
private static class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
this.next = null;
}
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
ListNode m1 = new ListNode(5);
ListNode m2 = new ListNode(8);
ListNode m3 = new ListNode(9);
m1.next = m2;
m2.next = m3;
ListNode c1 = new ListNode(1);
ListNode c2 = new ListNode(12);
c1.next = c2;
//c2.next = n1;
ListNode mergeNode = mergeLink(m1, c1);
//ListNode mergeNode2 = mergeLink(m1, c1);
//ListNode mergeNode = mergeSortedList(m1, c1);
printList(mergeNode);
//printList(mergeNode2);
System.out.println();
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
printList(n1);
Delete(n1, n5);
printList(n1);
// create a cycle
//n5.next = n3;
//n5.next = n6;
//n6.next = n4;
// System.out.println(hasCycle(n1));
// System.out.println(getListLength(n1));
// printList(n1);
//
// //n1 = reverseList(n1);
// n1 = reverseListRec(n1);
// printList(n1);
// ListNode ret = reGetKthNode(n1, 7);
// if (ret != null) {
// System.out.println(ret.val);
// } else {
// System.out.println("null");
// }
//reGetKthNodeRec(n1, 1);
// reGetKthNodeRec2(n1, 3);
// ListNode ret = getMiddleNode(n1);
//
// if (ret != null) {
// System.out.println(ret.val);
// }
//
// reversePrintListStackRec(n1);
// reversePrintListStack(n1);
// reversePrintListRev(n1);
//printList(n1);
System.out.println(isIntersect(n1, c1));
ListNode cross = getFirstCommonNode(n1, c1);
if (cross == null) {
System.out.println("null");
} else {
System.out.println(cross.val);
}
ListNode cross2 = getFirstNodeInCycleHashMap(c1);
if (cross2 == null) {
System.out.println("null");
} else {
System.out.println(cross2.val);
}
}
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
// 获得ListNode 的长度
public static int getListLength(ListNode head) {
if (head == null) {
return 0;
}
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
/*
* 反转链表
* 此算法亮点是:一次只需要处理把下一个节点指向curr,
* 不断循环,即可完成任务
* */
public static ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode next = head.next;
ListNode curr = head;
// 先把头节点的下一个指定.
curr.next = null;
// 每次只需要将curr的next指向curr即可,
// 终止条件是:next是null 表示我们将所有的节点进行了翻转
while (next != null) {
ListNode tmp = next.next;
next.next = curr;
curr = next;
next = tmp;
}
return curr;
}
// 翻转递归(递归)
// 递归的精髓在于你就默认reverseListRec已经成功帮你解决了子问题了!但别去想如何解决的
// 现在只要处理当前node和子问题之间的关系。最后就能圆满解决整个问题。
/*
head
1 -> 2 -> 3 -> 4
head
1--------------
|
4 -> 3 -> 2 // Node reHead = reverseListRec(head.next);
reHead head.next
4 -> 3 -> 2 -> 1 // head.next.next = head;
reHead
4 -> 3 -> 2 -> 1 -> null // head.next = null;
reHead
*/
public static ListNode reverseListRec(ListNode head) {
// if there is no node, or only one node, just return;
if (head == null || head.next == null) {
return head;
}
ListNode reHead = reverseListRec(head.next); // 先求解子问题。
head.next.next = head; // 将head 与被解决的子串的尾部相连。
head.next = null; // head的下一个必须指向 null,因为head 是新的尾部.
return reHead;
}
/**
* 查找单链表中的倒数第K个结点(k > 0)
* 最普遍的方法是,先统计单链表中结点的个数,然后再找到第(n-k)个结点。注意链表为空,k为0,k为1,k大于链表中节点个数时的情况
* 。时间复杂度为O(n)。代码略。 这里主要讲一下另一个思路,这种思路在其他题目中也会有应用。
* 主要思路就是使用两个指针,先让前面的指针走到正向第k个结点
* ,这样前后两个指针的距离差是k,之后前后两个指针一起向前走,前面的指针走到空时,后面指针所指结点就是倒数第k个结点
* when k = 1, it should be the last node.
*/
public static ListNode reGetKthNode(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode fast = head;
// 使fast and slow之间差 k
while (k > 0) {
if (fast == null) {
// 发生这种情况,说明k > sizeOfList.
return null;
}
fast = fast.next;
k--;
}
while (fast != null) {
fast = fast.next;
head = head.next;
}
return head;
}
/*
* 递归打印出倒数第k个节点。
* */
static int level = 0;
public static void reGetKthNodeRec(ListNode head, int k) {
if (head == null) {
return;
}
reGetKthNodeRec(head.next, k);
level++;
if (level == k) {
System.out.println(head.val);
}
}
/*
* 递归打印出倒数第k个节点。
* return: the length of the link.
* 此为改进的递归算法,使用此算法,不需要加入辅助变量。
* */
public static int reGetKthNodeRec2(ListNode head, int k) {
if (head == null) {
return 0;
}
int len = reGetKthNodeRec2(head.next, k);
if (len == k - 1) {
System.out.println(head.val);
}
return len + 1;
}
/**
* 判断一个单链表中是否有环
* 这里也是用到两个指针。如果一个链表中有环,也就是说用一个指针去遍历,是永远走不到头的。因此,我们可以用两个指针去遍历,一个指针一次走两步
* ,一个指针一次走一步,如果有环,两个指针肯定会在环中相遇。时间复杂度为O(n)
*/
public static boolean hasCycle(ListNode head) {
ListNode slow = head; // 快指针每次前进两步
ListNode fast = head; // 慢指针每次前进一步
// 如果fast没有到达尾部,那么slow也不会。所以不需要判定slow是不是null
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) { // 相遇,存在环
return true;
}
}
return false;
}
/*
* 4. 查找单链表的中间结点: getMiddleNode
* 这里只处理n个数为 奇数的情况
* 我们可以设置2个 指针,一个快,一个慢
* 1-2-3-null
* 当fast前进2n时,它到达3,链表长度是2n + 1
* 中间节点应为(2n+1)/2 + 1 = n + 1;
* 所以,slow节点前进n恰好可以到达中间。
*
* 边界:
* n = 1时,一开始就可以退出,仍然可以满足
* 此算法特点:
* 1->2->3->4
* 返回2
*/
public static ListNode getMiddleNode(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
/**
* 5. 从尾到头打印单链表: reversePrintListStack,reversePrintListRec(递归)
* @param head
* @return
*/
public static void reversePrintListStackRec(ListNode head) {
if (head == null) {
return;
}
// print the next first.
reversePrintListStackRec(head.next);
System.out.print(head.val + " ");
}
/**
* 从尾到头打印单链表
* 对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系统使用栈,也就是递归。注意链表为空的情况
* 。时间复杂度为O(n)
*
* 还有一种做法,是可以把链表反转,我们也可以从头到尾打印。
*/
public static void reversePrintListStack(ListNode head) {
if (head == null) {
return;
}
System.out.println();
Stack<Integer> s = new Stack<Integer>();
while (head != null) {
s.push(head.val);
head = head.next;
}
// print the next first.
while (!s.isEmpty()) {
System.out.print(s.pop() + " ");
}
}
/**
* 从尾到头打印单链表
* 是可以把链表反转,我们也可以从头到尾打印。 为了不影响原有的链表,可以再反转回来
*/
public static void reversePrintListRev(ListNode head) {
if (head == null) {
return;
}
ListNode rev = reverseList(head);
System.out.println();
// print the next first.
ListNode curr = rev;
while (curr != null) {
System.out.print(rev.val + " ");
curr = curr.next;
}
System.out.println();
//printList(rev);
reverseList(rev);
}
/*
* 6. 已知两个单链表pHead1 和pHead2 各自有序,把它们合并成一个链表依然有序: mergeSortedList, mergeSortedListRec
*
* 与merge sort思想类似.
* */
public static ListNode mergeSortedList(ListNode head1, ListNode head2) {
if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
// 作为头节点的前一个节点
ListNode dummyNode = new ListNode(0);
ListNode curr = dummyNode;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
curr.next = head1;
head1 = head1.next;
} else {
curr.next = head2;
head2 = head2.next;
}
curr = curr.next;
}
// 把没有取完的链直接接在结果上即可。
if (head1 != null) {
curr.next = head1;
} else {
curr.next = head2;
}
return dummyNode.next;
}
static class Node {
Node next;
int val;
Node (int val) {
this.val = val;
}
}
public static ListNode mergeLink (ListNode aLink, ListNode bLink) {
ListNode dummy = new ListNode(0);
ListNode root = dummy;
while (aLink != null && bLink != null) {
if (aLink.val < bLink.val) {
dummy.next = aLink;
dummy = aLink;
aLink = aLink.next;
} else {
dummy.next = bLink;
dummy = bLink;
bLink = bLink.next;
}
}
if (aLink != null) {
dummy.next = aLink;
} else {
dummy.next = bLink;
}
return root.next;
}
/*
* 先完成的算法,应该会简单一点儿。
* 简直是优雅的算法啊!太棒了!只不过 为什么自己很难想出这么棒的算法呢?
* 虽然递归的原理每个人都懂,但是写出漂亮的递归真的是考验功底呢。
*
* 精髓就是: 在每一次的Merge的处理时,只需要考虑merge一个元素,也就是提取出一个元素,而下一步的merge,交给下一步的recursion
* 来处理。
*/
public static ListNode mergeSortedListRec(ListNode head1, ListNode head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode headMerge = null;
if (head1.val < head2.val) {
headMerge = head1;
head1.next = mergeSortedListRec(head1.next, head2);
} else {
headMerge = head2;
head2.next = mergeSortedListRec(head1, head2.next);
}
return headMerge;
}
// http://fisherlei.blogspot.com/2013/11/leetcode-linked-list-cycle-ii-solution.html
// 更进一步,寻找环的起点,实际上,2点相遇后,我们再将某点放回起点,让它再走X的距离(X为起点到环的交点的距离),
// 即可让2个点相交在环的点处。
public static ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
ListNode n1 = head;
while (true) {
if (n1 == slow) { // 注意,要选判断,再移动,
return n1; // because 环的起点有可能就在开始的地方。
}
n1 = n1.next;
slow = slow.next;
}
}
}
return null;
}
/*
* * 8. 判断两个单链表是否相交: isIntersect
* http://blog.csdn.net/yunzhongguwu005/article/details/11527675
* 求两个单链表是否相交分三种情况讨论:
* 1,如果两个链表一个有环,一个无环则一定不相交
* 2.如果都没有环,则判断两个链表的最后节点是否相同,如果相同则相交,不相同则不相交。
* 3.如果都有环,则判断一个链表环里的节点是否是另一个链表环里的节点。如果是则相交,如果不是则不相交。
*
* 步骤如下:
* 1. 先判断2个链表有没有环。
* 2. 如果都没有环,查最后节点是否相同
* 3. 如果都有环,则将b链的环节点跑一圈,如果遇到A链中的节点,则返回true
*/
public static boolean isIntersect(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null) {
return false;
}
ListNode head1C = hasCycleRetNode(head1);
ListNode head2C = hasCycleRetNode(head2);
// 两个链表都是有环的。
if (head1C != null && head2C != null) {
ListNode tmp = head1C;
do {
// 放在前面判断,因为有可能当前节点就是要求的结果
if (head1C == head2C) {
return true;
}
// 跑一圈来找是不是同一个圈。
head1C = head1C.next;
} while (tmp != head1C);
return false;
// 两个链表都是没有环的
} else if (head1C == null && head2C == null){
while (head1.next != null) {
head1 = head1.next;
}
while (head2.next != null) {
head2 = head2.next;
}
// 无环的话,应该具有相同的尾节点.
return head1 == head2;
} else {
return false;
}
}
/**
* 如果有环,返回在环内的某节点。否则返回null
*/
public static ListNode hasCycleRetNode(ListNode head) {
if (head == null) {
return head;
}
ListNode s = head;
ListNode f = head;
while (f != null && f.next != null) {
f = f.next.next;
s = s.next;
if (f == s) {
return f;
}
}
return null;
}
/*
* * 9. 求两个单链表相交的第一个节点: getFirstCommonNode
* 分为2种情况:
*
* 1. 没有环的情况.
* 求两个单链表相交的第一个节点 对第一个链表遍历,计算长度len1,同时保存最后一个节点的地址。
* 对第二个链表遍历,计算长度len2,同时检查最后一个节点是否和第一个链表的最后一个节点相同,若不相同,不相交,结束。
* 两个链表均从头节点开始,假设len1大于len2
* ,那么将第一个链表先遍历len1-len2个节点,此时两个链表当前节点到第一个相交节点的距离就相等了,然后一起向后遍历,直到两个节点的地址相同。
* 时间复杂度,O(len1+len2)
*
* ---- len2
* |__________
* |
* --------- len1
* |---|<- len1-len2
*
* 2. 有环的情况
* (1). 交点在环上
* 这样子的话,实际上我们可以求出2个交点。我们只要判断2个交点是不是相等。不相等,把2个交点返回任何一个。
* (2). 交点不在环上,则计算出环的交点,然后len1 = 起点至环的交点,len2 = 起点至环的交点,然后如方法1相同的做法。
*/
public static ListNode getFirstCommonNode(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null) {
return null;
}
ListNode cross1 = detectCycle(head1);
ListNode cross2 = detectCycle(head2);
// There is no CIRCLE
if (cross1 == null && cross2 == null) {
int len1 = getListLength(head1);
int len2 = getListLength(head2);
//将长的链截短
if (len1 > len2) {
while (len1 > len2) {
head1 = head1.next;
len1--;
}
} else {
while (len2 > len1) {
head2 = head2.next;
len2--;
}
}
while (head1 != null) {
if (head1.next == head2.next) {
return head1.next;
}
}
return null;
} else if (cross1 != null && cross2 != null) {
return cross1;
}
return null;
}
/**
* 求进入环中的第一个节点 用HashSet做 一个无环的链表,它每个结点的地址都是不一样的。
* 但如果有环,指针沿着链表移动,那这个指针最终会指向一个已经出现过的地址 以地址为哈希表的键值,每出现一个地址,
只要出现重复的元素,就找到了环的交点.
*/
public static ListNode getFirstNodeInCycleHashMap(ListNode head) {
if (head == null) {
return null;
}
HashSet<ListNode> h = new HashSet<ListNode>();
while (head != null) {
if (h.contains(head)) {
return head;
} else {
h.add(head);
}
head = head.next;
}
return null;
}
/*
* 对于删除节点,我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点,这种情况需要遍历找到该节点的前一个节点,
* 时间复杂度为O(n)。对于链表,链表中的每个节点结构都是一样的,所以我们可以把该节点的下一个节点的数据复制到该节点,
* 然后删除下一个节点即可。要注意最后一个节点的情况,这个时候只能用常见的方法来操作,先找到前一个节点,
* 但总体的平均时间复杂度还是O(1)。参考代码如下:
* */
public static void Delete(ListNode head, ListNode toBeDeleted) {
if (head == null) {
return;
}
if (toBeDeleted.next != null) {
toBeDeleted.val = toBeDeleted.next.val;
toBeDeleted.next = toBeDeleted.next.next;
} else {
while (head != null) {
if (head.next == toBeDeleted) {
head.next = toBeDeleted.next;
return;
}
head = head.next;
}
}
return;
}
}