Description

如何判断两个有环单链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。如果两个链表长度分别为N和M,请做到时间复杂度O(N+M),额外空间复杂度O(1)。

给定两个链表的头结点head1head2(注意,另外两个参数adjust0adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。

Solutions

1. Different situation

  要分几个情况讨论!

# -*- coding:utf-8 -*-
# Time: O(n)
# Space: O(1)
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class ChkIntersection:
    def detectCycle(self, head):
        if not head:
            return None
        fast, slow = head, head
        while fast and slow:
            if fast.next:
                fast = fast.next.next
            else:
                return None
            slow = slow.next
            if fast == slow:
                break
        if not fast or not slow:
            return None
        restart = head
        while restart != slow:
            restart = restart.next
            slow = slow.next
        return slow
    
    def chkInter(self, head1, head2, adjust0, adjust1):
        point1 = self.detectCycle(head1)
        point2 = self.detectCycle(head2)
        node1, node2 = head1, head2
        n1, n2 = 0, 0
        while node1 != point1:
            node1 = node1.next
            n1 += 1
        while node2 != point2:
            node2 = node2.next
            n2 += 1
        diff = abs(n1 - n2)
        node1, node2 = head1, head2
        if n1 > n2:
            for _ in range(diff):
                node1 = node1.next
        else:
            for _ in range(diff):
                node2 = node2.next
        while node1 != point1 and node2 != point2:
            if node1 == node2:
                return node1
            node1 = node1.next
            node2 = node2.next
        
        node1 = point1
        while True:
            if node1 == point2:
                if n1 > n2:
                    return point2
                else:
                    return point1
            node1 = node1.next
            if node1 == point1:
                break
        return False

References

  1. 5.14 有环单链表相交判断