/
Intersection.java
69 lines (64 loc) · 2.45 KB
/
Intersection.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
package org.redquark.techinterview.ctci.linkedlists;
/**
* @author Anirudh Sharma
* <p>
* Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node.
* <p>
* Note that the intersection is defined based on reference, not value. That is, if the kth node of the
* first linked list is the exact same node (by reference) as the jth node of the second linked list,
* then they are intersecting.
*/
public class Intersection {
private static Node findIntersectingNode(Node head1, Node head2) {
// Length of lists
int firstListLength = 0;
int secondListLength = 0;
// Reference to both heads
Node firstListTraversal = head1;
Node secondListTraversal = head2;
// Loop over both lists
while (firstListTraversal != null) {
firstListLength++;
firstListTraversal = firstListTraversal.next;
}
while (secondListTraversal != null) {
secondListLength++;
secondListTraversal = secondListTraversal.next;
}
// Difference between the lengths
int difference = Math.abs(firstListLength - secondListLength);
// Reset both pointers
firstListTraversal = head1;
secondListTraversal = head2;
// Loop 'difference' number of nodes in the
// bigger list
if (firstListLength > secondListLength) {
for (int i = 0; i < difference; i++) {
firstListTraversal = firstListTraversal.next;
}
} else {
for (int i = 0; i < difference; i++) {
secondListTraversal = secondListTraversal.next;
}
}
// Loop until both the nodes are same
while (firstListTraversal != secondListTraversal) {
firstListTraversal = firstListTraversal.next;
secondListTraversal = secondListTraversal.next;
}
return firstListTraversal;
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
head1.next.next.next = new Node(4);
Node head2 = new Node(6);
head2.next = new Node(5);
head2.next.next = new Node(4);
head2.next.next.next = head1.next.next;
head2.next.next.next.next = new Node(2);
head2.next.next.next.next.next = new Node(1);
System.out.println(findIntersectingNode(head1, head2).data);
}
}