[leetcode] 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.

Let list a is 1 → 2 → 3 → 4 → 5 → 6 → 7 and list b is 1 → 2 → 5 → 6 → 7 , they have different lengths.
Note that new list A which is a joined with b and new list B which is b joined with a have the same lengths.
A:1 → 2 → 3 → 4 → 5 → 6 → 7 → 1 → 2 → 5 → 6 → 7
B:1 → 2 → 5 → 6 → 7 → 1 → 2 → 3 → 4 → 5 → 6 → 7
There are two kinds of situations：

• If a and b have intersection, then A and B will have some same node at the end of the list.Like above case, A and B have the same nodes 5 → 6 → 7
• If a and b have no intersection at all, like a is 1 → 2 → 3 → 4 → 5 and b is 6 → 7 → 8 → 9.
  A:1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9
  B:6 → 7 → 8 → 9 → 1 → 2 → 3 → 4 → 5    In this case, A and B have no same node.

Therefore, the original problem convert to a easy one: whether A and B linked list have same node, where A and B have same lengths.

#Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
#Generate a linked list by a list and return the head node
def gen_ListNode(li):
    if not li:
        return None
    head=ListNode(li.pop(0))
    tmp=head
    while li:
            tmp.next=ListNode(li.pop(0))
            tmp=tmp.next
    return head
#Print a linked list from head to tail
def show_List(head):
    if not head:
        print empty
    while head:
        print head.val,
        if head.next:
            print '→',
        head=head.next
    print 


head=gen_ListNode([1,2,3,4,5,6,7])
show_List(head)

1 → 2 → 3 → 4 → 5 → 6 → 7

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        pa,pb=headA,headB
        while pa is not pb:
            if pa:
                pa=pa.next
            else:
                pa=headB
            if pb:
                pb=pb.next
            else:
                pb=headA
        return pa

Status: Accepted
Runtime: 420 ms
Ranking: beats 25.27%