首页 > 编程学习 > 【算法100天 | 20】有环/无环链表的相交问题(Java实现)

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

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

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

复杂度要求:

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

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

在这里插入图片描述

思路

既然两个链表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;
}
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式