有环单链表相交判断、单链表相交判断

柔光的暖阳◎ 2022-06-09 04:59 211阅读 0赞

*   *   *  有环单链表相交判断
         *  单链表相交判断

--------------------

### 有环单链表相交判断 ###

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

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

**我的提交**  
（这题意描述的不清不楚啊！！！没看懂题意：到底要返回啥？？？）

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class ChkIntersection:
        def chkInter(self, head1, head2, adjust0, adjust1):
            # write code here
            loopa, lena = self.chkLoop(head1)
            loopb, lenb = self.chkLoop(head2)
    
            if loopa != loopb:
                pa = loopa
                pb = loopb
                while pa != pb and pa != loopa:
                    if pa == pb:
                        # 两个入环点都在环内
                        return pb
                    pa = pa.next
                return None
    
            else:
                pa, pb = None
                if lena > lenb:
                    pa, pb = head1, head2
                else:
                    pa, pb = head2, head1
    
                for _ in range(abs(lena - lenb)):
                    pa = pa.next
    
                while pa != pb:
                    pa = pa.next
                    pb = pb.next
                # 链表在入环前或入环时相交
                return pa
    
        def chkLoop(self, head):
            # 返回有环链表的入环结点和链表长度
            slow = head
            fast = head
            n = 1
            while True:
                slow = slow.next
                n += 1
                fast = fast.next.next
                if fast == slow:
                    break
    
            p = head
            while p != slow:
                p = p.next
                slow = slow.next
                n += 1
            return p, n

**参考答案**

--------------------

### 单链表相交判断 ###

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

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

**我的提交**

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class ChkIntersection:
        def getLoopNode(self, head):
            fast, slow = head, head
            while fast and fast.next:
                fast = fast.next.next
                slow = slow.next
                if slow == fast:
                    break
            if slow != fast:
                return None
            fast = head
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return fast
    
        def chkInter(self, head1, head2, adjust0, adjust1):
            # write code here
            if not head1 or not head2:
                return False
            loop1 = self.getLoopNode(head1)
            loop2 = self.getLoopNode(head2)
            cur1 = head1
            cur2 = head2
            if not loop1 and not loop1:
                while cur1.next:
                    cur1 = cur1.next
                while cur2.next:
                    cur2 = cur2.next
            if cur1 == cur2:
                return True
    
            if loop1 == loop2:
                return True
            cur = loop1.next
            while cur != loop1:
                if cur == loop2:
                    return True
                cur = cur.next
            return False