无环相交链表

Leetcode Link: 160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。 注意，函数返回结果后，链表必须保持其原始结构。

解法一

思路：相交的链表，他们的为尾节点一定是同一个内存。其相交的位置一定再长链表走了长度差步之后

题解：自己的版本

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        len1, len2 = 0, 0
        oriA, oriB = headA, headB
 
        # 不加也行，加了更快一点
        if headA.next==0 or headB.next ==0:
            return None
 
        while(headA.next != None or headB.next != None):
            if headA.next != None:
                len1 = len1 + 1
                headA = headA.next
            if headB.next != None:
                len2 = len2 + 1
                headB = headB.next
        # 比较两个尾节点是不是同一个地址，不是的话一定不会相交
        if headB != headA:
            return None
        # 让长的链表先走，相交的位置一定再diffLen之后。
        diffLen = abs(len1 - len2)
        fast = oriB if len2 > len1 else oriA
        slow = oriA if len2 > len1 else oriB
 
        for i in range(diffLen):
            fast = fast.next
        
        while(1):
            if fast == slow:
                return fast
            fast = fast.next
            slow = slow.next

解法二

思路：双指针（需要画图理解）

题解：时间复杂度 $O(M+N)$, 空间复杂度 $O(1)$

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        评论区一个很巧妙的方法，使两个链表到达相等位置时走过的是相同的距离
        链表1的长度是x1+y，链表2的长度是x2+y，我们同时遍历链表1和链表2，到达末尾时，再指向另一个链表。
        则当两链表走到相等的位置时：x1+y+x2 = x2+y+x1
        """
        p = headA
        q = headB
        while p!=q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p # 返回 q也是对，换句话说，pa,pb都是交点，为什么？

这是不是和有环的求环入口有点像？参考相关题目后整理

解法三

思路：哈希表，这个还是比较直观的

题解：时间复杂度 $O(M+N)$, 空间复杂度 $O(N)$

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        listA = set()
        while headA:
            listA.add(headA) # 所有节点放到表里
            headA = headA.next
        while headB:
            if headB in listA: #看看表里有没有
                return headB
            headB = headB.next
        return None

启发和联系