LeetCode#160 Intersection of Two Linked Lists

Problem Definition:

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.

Solution 1: Seems a little bit long, but it's straightforward.

 1 def getIntersectionNode( headA, headB):
 2         l1,l2=0,0
 3         ha,hb=headA,headB
 4         while ha!=None:
 5             ha=ha.next
 6             l1+=1
 7         while hb!=None:
 8             hb=hb.next
 9             l2+=1
10         ha,hb=headA,headB   #throwback
11         if l1>l2:
12             sub=l1-l2
13             while sub>0:
14                 ha=ha.next
15                 sub-=1
16         else:
17             sub=l2-l1
18             while sub>0:
19                 hb=hb.next
20                 sub-=1
21         while ha!=hb:
22             ha=ha.next
23             hb=hb.next
24         return ha

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

Solution 2：利用同样的原理，不同的解释。

1）同时遍历两个链表。ha遍历headA所指代链表,hb遍历headB所指代链表。

2）当ha到达链表尾时，将其指向headB，继续遍历；当hb到达链表尾时，将其指向headA，继续遍历。

3）当ha==hb时，返回ha。

　　看下面的栗子：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

ha从a1开始走到c3，然后指向b1。此时hb正指向c3。
下一时刻，ha到达b2，而hb到达a1。如此便达到了类似前一种解法中的（使得两链表从到末节点距离相同的两个节点开始遍历）效果
继续遍历就会到达c1。

在以上过程中，每一步（ha和hb都移动后）都判断ha==hb，一旦成立则立即返回。
因此会有以下不同情况
1）两表有公共子链，但两表不等长，则在第二轮遍历时会找到交叉节点
2）两表有公共子链，且两表等长，则在第一轮遍历时就能找到交叉节点
3）两表没有公共子链，则在第一轮或者第二轮遍历中同时变为空，相等，返回空

代码：

1 def getIntersectionNode( headA, headB):
2     ha,hb=headA,headB
3     while ha!=hb:
4         ha=ha.next if ha!=None else headB
5         hb=hb.next if hb!=None else headA
6     return ha