Description

给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。

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

Solutions

1. Direct

  先得判断是否有环,分几个情况讨论,如果两个都没有环,就调用无环单链表是否相交的判断方法;如果一个有环、一个没环,说明不可能相交;如果两个都有环就调用有环的判断。

# -*- coding:utf-8 -*-
# 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 chk_cycle_Inter(self, head1, head2):
        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
    def chkIntersect(self, headA, headB):
        # no cycle
        if not headA or not headB:
            return None
        size_a, size_b = 0, 0
        nodeA, nodeB = headA, headB
        while nodeA:
            size_a += 1
            nodeA = nodeA.next
        while nodeB:
            size_b += 1
            nodeB = nodeB.next
        nodeA, nodeB = headA, headB
        if size_a == size_b:
            pass
        elif size_a > size_b:
            steps = size_a - size_b
            for _ in range(steps):
                nodeA = nodeA.next
        else:
            steps = size_b - size_a
            for _ in range(steps):
                nodeB = nodeB.next
        while nodeA and nodeB:
            if nodeA == nodeB:
                return nodeA
            nodeA = nodeA.next
            nodeB = nodeB.next
        return None
    def chkInter(self, head1, head2, adjust0, adjust1):
        # write code here
        point1 = self.detectCycle(head1)
        point2 = self.detectCycle(head2)
        if (not point1 and point2) or (not point2 and point1):
            return False
        elif not point1 and not point2:
            return self.chkIntersect(head1, head2)
        else:
            return self.chk_cycle_Inter(head1, head2)

References

  1. 5.15 单链表相交判断