160. 相交链表(Easy)

题目描述

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

做题链接：面试题52. 两个链表的第一个公共节点、160. 相交链表

样例

样例1

样例2

解题思路

方法一：哈希表

空间复杂度 $O(N)$ 不满足 $O(1)$ 的条件

最容易想到的一个想法，首先A先走一遍，把所有节点记录在哈希表里。然后B走一遍，看看公共节点。

方法二：双指针法

此类问题，首先考虑的是 双指针法 ，同 面试题22. 链表中倒数第k个节点 类似

其实总结起来就是：起点虽然不一样，但路程一样，终点一样,速度一样，必定同时到达！其中，路程是构思的关键点。

代码

哈希表

class Solution:
    """ 哈希表, 但是不满足空间 O(N) 要求 """
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        hash_table = set()
        while headA:
            hash_table.add(headA)
            headA = headA.next
        while headB:
            if headB in hash_table: return headB
            else: headB = headB.next

双指针法

# 当不相交的时候会死循环
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB: return 
        p1 = headA
        p2 = headB
        while True:
            p1 = p1.next if p1.next else headB
            p2 = p2.next if p2.next else headA
            if p1 == p2: 
                break 
        return p1 

换个思路，走的时候，允许走到 null 值，最后 node1 和 node 2 由于路程是一样的，一定会相等的。

# AC版
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node1, node2 = headA, headB
        while node1 != node2:
            node1 = node1.next if node1 else headB
            node2 = node2.next if node2 else headA
        return node1

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    p1, p2 := headA, headB
    for p1 != p2 {
        if p1 == nil {
            p1 = headB
        }else {
            p1 = p1.Next
        }
        if p2 == nil {
            p2 = headA
        }else {
            p2 = p2.Next
        }
    }
    return p1 
}