【算法100天 | 20】有环/无环链表的相交问题（Java实现）

Myth丶恋晨 2023-09-24 14:24 39阅读 0赞

### 若两个链表相交，请返回相交的第一个节点。 ###

给定两个有可能有环也有可能无环的单链表，头节点head1和head2。

实现一个函数，如果两个链表相交，请返回相交的第一个节点（从这个节点开始，后续结构都一样）。如果不相交，返回null。

**复杂度要求：**

*  如果两个链表长度之和为N，要求：时间复杂度为O(n)，额外空间复杂度为O(1)。

该题目可以理解为`LeetCode 160. 相交链表`的升级版，因为LeetCode160题中的链表是无环的，所以就简单了很多！！

![在这里插入图片描述][2106eede4ee14283adba652427b0900b.png]

#### 思路 ####

既然两个链表head1、head2可能有环，也可能无环，我们先判断这两个链表到底是不是有环链表，这是会有三种情况：

*  一个链表有环、一个链表无环。
 *  两个链表都无环。
 *  两个链表都有环。

第一种情况（一个链表有环、一个链表无环）最简单，两个链表肯定不相交。

第二种情况（两个链表都无环），判断两个链表长度的差值x，长的链表先往后走x步，然后再让两个链表一起往后走，如果两个链表当前节点不相等就一直到往后走，直到走到链表尾部。

第三种情况（两个链表都有环），最复杂，其中又细分三种情况。

> 1> 第一种情况：两个链表不相交，各玩个的。  
> 2> 第二种情况：两个链表相交了，相交节点在入环节点 及其之前（即：入环节点是同一个）。则以入环节点为尾，计算前面链表的长度；然后再和无环链表相交一样处理。
> 
>  *  入环节点的查找方式：
>     
>     >  *  快慢指针法，快慢指针同时从head出发，判断出链表是有环链表。
>     >  *  slow从相交节点开始继续走、fast节点放到head继续往后走，都每次走一步，则它俩相遇的节点是链表环的第一个节点。  
>     >     3> 第三种情况：两个链表相交了，但入环节点不是同一个；
>  *  假设head1的入环节点为loopNode1，head2的入环节点为loopNode2。
>  *  从loopNode1开始在环里转，如果能遇到loopNode2，返回loopNode1；
>  *  如果都转了一圈了，也找不到loopNode2，那就是两个链表不相交。
>  *  注意：可以返回loopNode1，也可以返回loopNode2。

#### 代码 ####

/**
     * 方法二：不使用容器
     * 时间复杂度为O(n)，额外空间复杂度为O(1)。
     */
    public static ListNode getIntersectNode(ListNode head1, ListNode head2) {
        
        if (head1 == null || head2 == null) {
        
            return null;
        }
        // head1's first into loop node
        ListNode loopNode1 = getLoopNode(head1);
        ListNode loopNode2 = getLoopNode(head2);
    
        // both no_loop
        if (loopNode1 == null && loopNode2 == null) {
        
            return noLoop(head1, head2);
        }
    
        // both loop
        if (loopNode1 != null && loopNode2 != null) {
        
            /**
             * 几种情况：
             *     1) 两个链表不相交，各自玩自己的
             *     2) 两个链表相交了，相交节点在入环节点 及其之前（即：入环节点是同一个）。
             *           以入环节点为尾，计算前面链表的长度，然后和无环链表相交一样处理。
             *     3）两个链表相交了，入环节点不是同一个
             *         从loopNode1开始在环里转，如果能遇到loopNode2，返回loopNode1；如果都转了一圈了，也找不到loopNode2，那就是两个链表不相交
             *         可以返回loopNode1，也可以返回loopNode2
             */
            return bothLoop(head1, loopNode1, head2, loopNode2);
        }
    
        // one loop another no_loop
        return null;
    }
    
    private static ListNode noLoop(ListNode head1, ListNode head2) {
        
    
        // n -> head1 and head2 's count of difference nodes
        int n = 0;
        ListNode curr1 = head1;
        ListNode curr2 = head2;
        while (curr1.next != null) {
        
            n++;
            curr1 = curr1.next;
        }
        while (curr2.next != null) {
        
            n--;
            curr2 = curr2.next;
        }
        // tail node is different ，must not intersect
        if (curr1 != curr2) {
        
            return null;
        }
    
        // head1 and head2 who more long who curr1, else curr2
        curr1 = n > 0 ? head1 : head2;
        curr2 = curr1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n > 0) {
        
            n--;
            curr1 = curr1.next;
        }
        while (curr1 != curr2) {
        
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        return curr1;
    }
    
    /**
     * both head is loop
     *
     * @param loop1 head1's first into loop node
     * @param loop2 head2's first into loop node
     */
    private static ListNode bothLoop(ListNode head1, ListNode loop1, ListNode head2, ListNode loop2) {
        
        if (loop1 == loop2) {
        
            int n = 0;
            ListNode curr1 = head1;
            ListNode curr2 = head2;
            while (curr1 != loop1) {
        
                n++;
                curr1 = curr1.next;
            }
            while (curr2 != loop2) {
        
                n--;
                curr2 = curr2.next;
            }
    
            // head1 and head2 who more long who curr1, else curr2
            curr1 = n > 0 ? head1 : head2;
            curr2 = curr1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n > 0) {
        
                n--;
                curr1 = curr1.next;
            }
            while (curr1 != curr2) {
        
                curr1 = curr1.next;
                curr2 = curr2.next;
            }
            return curr1;
        } else {
        
            ListNode curr1 = loop1.next;
            while (curr1 != loop1) {
        
                if (curr1 == loop2) {
        
                    return loop1;
                }
                curr1 = curr1.next;
            }
        }
        return null;
    }
    
    
    /**
     * 找到链表的第一个入环节点，如果无环返回null。
     */
    public static ListNode getLoopNode(ListNode head) {
        
        if (head == null || head.next == null) {
        
            return null;
        }
        // slow and fast pointer go one step
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (slow != fast) {
        
            // no_loop
            if (fast.next == null || fast.next.next == null) {
        
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        /**
         * find first into loop node
         *     1) slow go from intersect node, step equal 1
         *     2) fast become head, and go, stop equal 1, until fast = slow.
         */
        fast = head;
        while (slow != fast) {
        
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

[2106eede4ee14283adba652427b0900b.png]: https://img-blog.csdnimg.cn/2106eede4ee14283adba652427b0900b.png