Description
给定两个单链表的头节点head1和head2，如何判断两个链表是否相交？相交的话返回true，不想交的话返回false。
给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个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)