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.

Notes:

• If the two linked lists have no intersection at all, return null.

• 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.

Credits: Special thanks to @stellari for adding this problem and creating all test cases.

Thoughts:

1. 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.

Code

# 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