乐趣区

关于算法:有环或无环单链表的相交问题

对于求有环无环单链表相交的问题,是链表类型题目中首屈一指的难题,且听一一道来。

一、题目形容

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

请实现一个函数,如果两个链表相交,请返回相交的第一个节点。如果不相交,返回 null

要求:如果两个链表长度之和为 N,工夫复杂度请达到 O(N),额定空间复杂度请达到 O(1)。

二、思路

解决思路分为两大步:

(1)找到单链表的入环节点,无环则返回 null

(2)依据失去的链表的入环节点,再展开讨论

1、找到单链表的入环节点,无环则返回 null

(1)遍历此单链表,如果某次遍历到的节点为 null,则此单链表必然无环

(2)否则有环

筹备一个快指针,一个慢指针。开始时,两个指针都从头节点开始,快指针一次走两个节点,慢指针一次走一个节点,直到两个指针相遇。

此时,快指针再从头节点开始走,每次走一个节点;慢指针从相遇处持续往下走,仍然一次走一个节点,当两个指针再次相遇时的节点即是入环节点。

2、依据失去的链表的入环节点,再展开讨论

(1)两个链表都无环

遍历其中一个链表,记录链表的长度 length1 和最初一个节点 end1;遍历另外一个链表,记录链表的长度 length2 和最初一个节点 end2。

如果 end1 和 end2 不等,则两个链表肯定不相交;否则,计算 length1 和 length2 的差值 a,长链表先走 a 个节点,而后两个链表挨个往下走,第一个相等的节点即是相交的第一个节点。

(2)一个有环、一个无环

此种状况两个链表是不可能相交的。(大伙能够尝试脑补出这样的构造, 记住一点,是单链表

(3)两个链表都有环

分三种状况,各自有环然而不相交;入环节点是同一个;入环节点有两个。

1)各自有环然而不相交

2)入环节点是同一个

3)入环节点有两个

两个链表的入环节点相等:即入环节点是同一个这种状况,求解过程和两个链表都是无环且相交的过程是一样的,也就是求解时齐全能够疏忽前面的环。

两个链表的入环节点不等:则是第一小种或第三小种。此时,从其中一个入环节点开始,遍历一圈,如果在回到本人时遇到了第二个入环节点,则是第三小种,否则就是第一小种。

三、具体参考代码

1、找到单链表的入环节点

/**
 * 找到单链表的入环节点,无环则返回 null
 *
 * @author Java 和算法学习:周一
 */
public static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}
    // 快指针
    Node fast = head.next.next;
    // 慢指针
    Node slow = head.next;
    while (fast != slow) {
        // 如果某次快指针走着走着变为空了,则此单链表必然无环
        if (fast.next == null || fast.next.next == null) {return null;}
        fast = fast.next.next;
        slow = slow.next;
    }

    // 当快慢指针相遇时,快指针再次从头节点开始走
    fast = head;
    while (fast != slow) {
        // 此时就不须要再判断为空了,能走到这里则此单链表必然是有环的
        // 此时快指针一次走一个节点
        fast = fast.next;
        // 慢指针仍然一次走一个节点
        slow = slow.next;
    }

    return slow;
}

2、依据失去的链表的入环节点,再展开讨论

(1)两个链表都无环

/**
 * 当初曾经晓得两个链表无环,找到它们的第一个相交节点
 *
 * @author Java 和算法学习:周一
 */
public static Node noLoop(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}

    Node current1 = head1;
    Node current2 = head2;
    int n = 0;
    // 链表一遍历一遍失去长度、最初一个节点
    while (current1.next != null) {
        n++;
        current1 = current1.next;
    }

    // 链表二遍历一遍失去长度差、最初一个节点
    while (current2.next != null) {
        n--;
        current2 = current2.next;
    }

    // 如果两个链表的最初一个节点不等,则肯定不相交
    if (current1 != current2) {return null;}

    // 长链表的头节点给 current1
    current1 = n > 0 ? head1 : head2;
    // 短链表的头节点给 current2
    current2 = current1 == head1 ? head2 : head1;

    n = Math.abs(n);
    // 长链表先走 n 个节点
    while (n != 0) {
        n--;
        current1 = current1.next;
    }

    // 两个链表挨个往下走,第一次相等的节点即是第一个相交的节点
    while (current1 != current2) {
        current1 = current1.next;
        current2 = current2.next;
    }

    return current1;
}

(3)两个链表都有环

/**
 * 两个链表都有环
 * 分三种状况,各自有环然而不相交;入环节点是同一个;入环节点有两个     
 *
 * @author Java 和算法学习:周一
 */
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    Node current1 = null;
    Node current2 = null;
    if (loop1 == loop2) {
        current1 = head1;
        current2 = head2;
        int n = 0;
        // 计算 head1 链表有多少个节点
        while (current1 != loop1) {
            n++;
            current1 = current1.next;
        }

        // 计算两个链表节点数的差值
        while (current2 != loop2) {
            n--;
            current2 = current2.next;
        }

        // 长链表的头节点给 current1
        current1 = n > 0 ? head1 : head2;
        // 短链表的头节点给 current2
        current2 = current1 == head1 ? head2 : head1;

        n = Math.abs(n);
        // 长链表先走 n 个节点
        while (n != 0) {
            current1 = current1.next;
            n--;
        }

        // 两个链表挨个往下走,第一次相等的节点即是第一个相交的节点
        while (current1 != current2) {
            current1 = current1.next;
            current2 = current2.next;
        }

        return current1;
    } else {
        // 两个链表的入环节点不等,则是各自有环然而不相交或者入环节点有两个
        current1 = loop1.next;
        // 从其中一个入环节点开始,遍历一圈,如果在回到本人时遇到了第二个入环节点,则是 入环节点有两个
        while (current1 != loop1) {if (current1 == loop2) {
                // 此时两个入环节点都是第一个相交节点,返回其中一个即可
                return loop1;
            }
            current1 = current1.next;
        }
        return null;
    }
}

以上是外围具体参考代码,置信主办法和测试方法可能轻易的写进去,当然想参考全副代码,此处也附上本文全副代码的 Github 地址:

https://github.com/monday-pro…

退出移动版