题目描述

编写一个程序，找到两个单链表相交的起始节点。

例如，下面的两个链表：

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

在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

最优解法——双指针（AC）

求出链表长度的差值，长链表的指针先想后移动lenA-lenB。然后两个链表一起往后走，若结点相同则第一个相交点。
时间复杂度O(n)，空间复杂度O(1)
Beat 97%

# 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
        """
        lengthA = 0
        lengthB = 0
        
        tempA = headA
        tempB = headB
        while(tempA):
            lengthA += 1
            tempA = tempA.next
            
        while(tempB):
            lengthB += 1
            tempB = tempB.next
            
        if(lengthA < lengthB):
            lengthA,lengthB = lengthB,lengthA
            headA,headB = headB,headA
            
        cha = lengthA - lengthB
        while(cha != 0):
            headA = headA.next
            cha -= 1
            
        while(headA and headB):
            if(headA == headB):
                return headA
            headA = headA.next
            headB = headB.next
            
        return None

参考答案

https://leetcode.com/problems/intersection-of-two-linked-lists/solution/