713544. Intersection Point in Y Shaped Linked Lists
Intersection Point in Y Shaped Linked Lists
Summary
The problem involves finding the intersection point between two linked lists that are part of a larger "Y" shaped structure. The two linked lists share a common node, but their lengths may vary. The goal is to find this shared node.
Detailed Explanation
The approach to solve this problem is to first find the length of both linked lists by counting the number of nodes in each list. Then, we can adjust the pointers of one of the lists so that it starts at a point where both lists are aligned, effectively allowing us to compare the nodes from both lists simultaneously.
Here's a step-by-step breakdown:
- Find the lengths of both linked lists using a simple loop.
- Adjust the pointer of one of the lists (let's say
list1) so that it points to the node at a distance equal to the length difference between the two lists minus 1. This is because we want to align the pointers in such a way that they point to the same node whenlist1andlist2are traversed simultaneously. - Now, traverse both linked lists simultaneously using two pointers (
p1forlist1andp2forlist2). As long asp1andp2are not equal (i.e., they don't point to the same node), move them forward one step each. - When
p1andp2become equal, it means we have found the intersection point.
Time complexity: O(N + M) where N and M are the lengths of the two linked lists. Space complexity: O(1) as no extra space is used.
list1 | list2
/ \ /
/ \ /
+----+--------+ +----+--------+
| | | | | |
| A | B C D | | E | F G H I |
+----+--------+ +----+--------+
In this example, the intersection point is node E. The lengths of the two linked lists are 5 and 3 respectively. We adjust the pointer of one of the lists so that it points to the node at a distance equal to the length difference minus 1 (in this case, 2 nodes ahead). Then, we traverse both lists simultaneously until we find the intersection point.
Optimized Solutions
Java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
int lenA = 0;
int lenB = 0;
ListNode p1 = headA;
while (p1 != null) {
lenA++;
p1 = p1.next;
}
ListNode p2 = headB;
while (p2 != null) {
lenB++;
p2 = p2.next;
}
p1 = headA;
for (int i = 0; i < lenA - lenB; i++) {
p1 = p1.next;
}
p2 = headB;
for (int i = 0; i < lenB - lenA; i++) {
p2 = p2.next;
}
while (p1 != null && p2 != null) {
if (p1 == p2) return p1;
p1 = p1.next;
p2 = p2.next;
}
return null;
}