原题

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.

 

解题思路

思路一：

1. 求出A和B两个链表的长度，取两者长度差，因为相等部分的长度肯定是相同的，所以将较长的链表遍历长度差，之后同时遍历A和B即可。

 

思路二：

1. 思路一的升级版，非常巧妙的一个算法，虽然A和B的长度不一定相等，但是A+B的长度是一样的
2. 所以就利用了在A链表后连B链表的方法（B同理）
3. 这样在第二次迭代遍历时就消除了长度差，如果有相同节点则为答案
4. 如果没有相同节点，那么A和B的末尾就是None相等，返回None

 

完整代码

思路一：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def getIntersectionNode(self, headA, headB):        """        :type head1, head1: ListNode        :rtype: ListNode        """        A = headA        B = headB        lengthA = self.lengthLink(A)        lengthB = self.lengthLink(B)        value = lengthA - lengthB                for i in xrange(abs(value)):            if value >= 0:                A = A.next            else:                B = B.next                        while A != B:            A = A.next            B = B.next                    return A                    def lengthLink(self, node):        length = 0        while node:            length += 1            node = node.next        return length

　　

思路二：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def getIntersectionNode(self, headA, headB):        """        :type head1, head1: ListNode        :rtype: ListNode        """        if headA == None or headB == None:            return None                a = headA        b = headB        # if a & b have different len, then we will stop the loop after second iteration        while a!=b:            # for the end of first iteration, we just reset the pointer to the head of another linkedlist            a = headB if a == None else a.next            b = headA if b == None else b.next                    return a