160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
- If the two linked lists have no intersection at all, return
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Special thanks to @stellari for adding this problem and creating all test cases.
- Having two traversors traverse two lists separately, the total path they travel will be equal. And if a in the first round first gets the end, b will catch up with exactly shorter distance in the second round. So if there is a intersection and even two lists are not of the same length, swapping the end/ starting point in the second round will make sure they will have the same distance to the end point in the second round.
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ if not headA or not headB: return None a, b = headA, headB while a != b: a = a.next if a else headB b = b.next if b else headA return a