-
Notifications
You must be signed in to change notification settings - Fork 2
/
IntersectionOfTwoLinkedLists.java
96 lines (83 loc) · 2.78 KB
/
IntersectionOfTwoLinkedLists.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
package LinkedList._160_Intersection_Of_Two_Linked_Lists;
import DataStructure.ListNode;
import static java.lang.Math.abs;
/**
* Created by hengwang on 2017-06-02.
*/
public class IntersectionOfTwoLinkedLists {
/**
* What's the characteristic of the two list after the node right before the intersection ?
* What about the length ?
* @param headA
* @param headB
* @return
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// Get the lengths of two lists
ListNode currentA = headA;
ListNode currentB = headB;
int lengthA = 0;
int lengthB = 0;
while (currentA != null) {
lengthA++;
currentA = currentA.next;
}
while (currentB != null) {
lengthB++;
currentB = currentB.next;
}
// Move the longer list to align with the shorter one
int gap = lengthA - lengthB;
ListNode runnerA = headA;
ListNode runnerB = headB;
if (gap >= 0) {
for (int i = 0; i < gap; i++) {
runnerA = runnerA.next;
}
} else {
for (int i = 0; i < abs(gap); i++) {
runnerB = runnerB.next;
}
}
// Now two lists have same length, move one at a time and compare
while (runnerA != null) {
if (runnerA == runnerB) {
return runnerA;
}
runnerA = runnerA.next;
runnerB = runnerB.next;
}
return null;
}
/**
* From LeetCode solution!
* Actually we don't care about the "value" of difference, we just want to make sure two pointers reach the
* intersection node at the same time.
* We can use two iterations to do that. In the first iteration, we will reset the pointer of one linkedlist to the
* head of another linkedlist after it reaches the tail node. In the second iteration, we will move two pointers
* until they points to the same node. Our operations in first iteration will help us counteract the difference.
* So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. If the
* two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node
* of both lists, which is null.
*
* @param headA
* @param headB
* @return
*/
public ListNode getIntersectionNode_NoLengthDifference(ListNode headA, ListNode headB) {
//boundary check
if (headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
//if a & b have different len, then we will stop the loop after second iteration
while (a != b) {
//for the end of first iteration, we just reset the pointer to the head of another linkedlist
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}