寻找链表相交结点问题

时间:2022-11-25 21:06:48

作者:Grey

原文地址:

博客园:寻找链表相交结点问题

CSDN:寻找链表相交结点问题

题目描述

给定两个可能有环也可能无环的单链表,头节点head1和head2。请实现一个函数,如果两个链表相交,请返回相交的 第一个节点。如果不相交,返回 null。

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

类似问题

见:寻找链表的入环节点和相交节点问题

本题主要的难点是要分析所有可能的情况,因为题目中提到「可能有环也可能无环」。

主要思路

先看大的情况,有如下三种情况

第一种情况:两个链表均无环;

第二种情况:两个链表均有环;

第三种情况:一个有环,一个无环。

首先,第三种情况下,两个链表一定不相交。针对第一种情况,就是寻找链表的入环节点和相交节点问题中提到LeetCode 160. Intersection of Two Linked Lists,现在只分析第二种情况。

由于两个链表都有环,两个链表如果相交,一定只有如下三种情况

情况1:两个链表独立不相交

寻找链表相交结点问题

情况2:两个链表的入环结点是同一个

寻找链表相交结点问题

情况3:两个链表的入环结点不是同一个,此时任意一个链表的入环结点都是相交结点。

寻找链表相交结点问题

先从最简单的情况1和情况3进行分析,情况一发生的条件是:两个链表的入环结点(loop1,loop2)不是同一个,判断条件很简单,就是从任意一个链表的入环结点开始遍历一圈,如果都没有遇到另外一个链表的入环结点, 两个链表不相交,属于情况1;

如果从任意一个链表的入环结点开始遍历一圈,遇到了另外一个链表的入环结点,则说明两个链表相交,属于情况3,且任意一个链表的入环结点都是相交结点。

最后分析情况2,两个链表的入环结点如果是同一个,可以记录两个链表的差值,然后让短链表先走差值步以后,长短链表同时开始走,相遇的结点就是第一个相交结点。

完整代码见:

public class Code_FindFirstIntersectNode {
    public static class List {
        public int val;
        public List next;

        public List(int v) {
            val = v;
        }
    }

    public static List getIntersectNode(List head1, List head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        // 两个均无环
        List loop1 = getLoopNode(head1);
        List loop2 = getLoopNode(head2);
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        // 两个均有环
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }

        // 一个有环一个无环 ,不可能相交
        return null;
    }

    // 找到链表第一个入环节点,如果无环,返回null
    public static List getLoopNode(List head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        // 慢指针 在第一个节点位置
        List slow = head.next;
        // 快指针,在第二个节点的位置
        List fast = head.next.next;

        while (slow != fast) {
            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;
    }

    // 如果两个链表都无环,返回第一个相交节点,如果不想交,返回null
    public static List noLoop(List head1, List head2) {
        if (head1 == null || head1 == null) {
            return null;
        }
        // 判断两个链表的长度


        int n = 0;
        List t1 = head1;
        List t2 = head2;
        while (t1.next != null) {
            n++;
            t1 = t1.next;
        }


        while (t2.next != null) {
            n--;
            t2 = t2.next;
        }

        // 两个链表的末节点不相等
        if (t2 != t1) {
            return null;
        }
        // 记录长的链表头节点
        List longer = n > 0 ? head1 : head2;
        // 记录短的链表头节点
        List shorter = longer == head1 ? head2 : head1;
        // 先让长链表走一段距离(这段的长度就是长链表和短链表的长度差)
        int gap = Math.abs(n);
        while (gap != 0) {
            gap--;
            longer = longer.next;
        }
        // 然后长链表和短链表同时开始走,直到相等的节点即为交点
        while (longer != shorter) {
            longer = longer.next;
            shorter = shorter.next;
        }
        return shorter;
    }

    // 两个有环链表,返回第一个相交节点,如果不想交返回null
    public static List bothLoop(List head1, List loop1, List head2, List loop2) {
        // 只有两种情况

        if (loop1 == loop2) {
            // 1. 未入环就相交
            // 这种情况下,两个链表的入环节点是一样
            int n = 0;
            List t1 = head1;
            List t2 = head2;
            while (t1 != loop1) {
                n++;
                t1 = t1.next;
            }
            while (t2 != loop2) {
                n--;
                t2 = t2.next;
            }

            List longer = n > 0 ? head1 : head2;
            List shorter = longer == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                longer = longer.next;
            }
            while (longer != shorter) {
                longer = longer.next;
                shorter = shorter.next;
            }
            return shorter;
        } else {
            // 2. 共用环,不在入环处相交,随便一个链表的入环点就是交点
            // loop1 != loop2
            // 从loop1开始,转一圈回到loop1
            // 如果都没有遇到loop2,则不相交
            // 如果遇到了loop1,则交点为loop1或者loop2都可以

            List t1 = loop1.next;
            while (t1 != loop1) {
                if (t1 == loop2) {
                    return loop1;
                }
                t1 = t1.next;
            }
            return null;

        }
    }
}

更多

算法和数据结构笔记