Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. 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.
Hint
- You can do this in O(A+B) time and O(1) additional space. That is, you do not need a hash table (although you could do it with one).
- Examples will help you. Draw a picture of intersecting linked lists and two equivalent linked lists (by value) that do not intersect.
- Focus first on just identifying if there's an intersection.
- Observe that two intersecting linked lists will always have the same last node. Once they intersect, all the nodes after that will be equal.
- You can determine if two linked lists intersect by traversing to the end of each and comparing their tails.
- Now, you need to find where the linked lists intersect. Suppose the linked lists were the same length. How could you do this?
- If the two linked lists were the same length, you could traverse forward in each until you found an element in common. Now, how do you adjust this for lists of different lengths?
- Try using the difference between the lengths of the two linked lists.
- If you move a pointer in the longer linked list forward by the difference in lengths, you can then apply a similar approach to the scenario when the linked lists are equal.
Solution
本题要我们求出两个链表的交汇点，假设两个链表等长的话，那么使用两个指针同时遍历必然会有指向同一个结点的情况，那就是我们要找的交汇点。进一步假设两个链表不等长的话，我们只需要先分别计算出两个链表的长度差 k，让长链表的指针先移动 k 个位置，然后两个链表一起移动，此时就相当于它们等长了，若第一次相遇则就是交汇点。
还有一种非常巧妙的写法，我们让两条链表分别从各自的开头开始往后遍历，当其中一条遍历到末尾时，我们跳到另一个条链表的开头继续遍历。两个指针最终会相等，而且只有两种情况，一种情况是在交点处相遇，另一种情况是在各自的末尾的空节点处相等。因为两个指针走过的路程相同，就是两个链表的长度之和。
public ListNode getIntersectionNode(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null) return null;
ListNode l1 = head1, l2 = head2;
while (l1 != l2) {
l1 = l1 == null ? head2 : l1.next;
l2 = l2 == null ? head1 : l2.next;
}
return l1;
}
