【链表】两个单链表相交的一系列问题

这是我参与更文挑战的第1天，活动详情查看： 更文挑战

题目

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

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

思路

1.首先分成三种大情况

1.1 head1和head2都没有环

1.2 head1和head2都有环

1.3 head1和head2中一个有环一个没有环

2.我们使用一个函数getLoop判断某个链表是否有环。

这个函数主要运用了快慢指针的方法，每次慢指针走一步，快指针走两步，如果这个链表有环的话，快指针会和慢指针相遇，如果没有环的话快指针会先为null

  public Node getLoop(Node head) { //查看该链表是否有环
        if (head == null || head.next == null || head.next.next == null) return null;
        Node slow = head.next;
        Node 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 fast;
    }
复制代码

3.根据getLoop的结果我们按照1中的分类分别进行处理

1.两个链表都没有环的话，能够相交的情况是只有这一种,对应noLoop方法

2.两个链表都有环的话，能够相交的情况有两种,对应bothLoop方法

3.head1和head2中一个有环一个没有环不可能有相交节点

解题技巧

得到第一个入环节点的方法

链表有环的情况下,每次慢指针走一步，快指针走两步，快指针会和慢指针相遇,相遇之后,快指针从头开始每次走一步，慢指针继续每次走一步，它们相遇的地方就是第一个入环节点

得到两个无环链表的交点的方法

 public Node noLoop(Node head1, Node head2) {
        int n = 0;
        Node n1 = head1;
        while (n1 != null) {
            n1 = n1.next;
            n++;
        }
        Node n2 = head2;
        while (n2 != null) {
            n2 = n2.next;
            n--;
        }
        if (n1 != n2) return null; //这个时候如果不是公共节点说明是两个不相交的链表
        n1 = n > 0 ? head1 : head2;
        n2 = n1 == head1 ? head2 : head1;
        //让n1变成长的那个链表
        n = Math.abs(n);
        while (n != 0) {
            n1 = n1.next;
            n--;
        }
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }
复制代码

1.首先遍历链表head1，用n记录长度

2.遍历链表head2,n记录head1和head2的长度差

3.让长度较长的链表先走n步,然后两个链表的指针再同时走直到相遇的地方就是交点

代码

public Node findFirstIntersectNode(Node head1, Node head2) {
        Node loop1 = getLoop(head1);
        Node loop2 = getLoop(head2);
        if (loop1 == null && loop2 == null) {//大情况一：同时无环
            System.out.println("noLoop");
            return noLoop(head1, head2);
        }
        if (loop1 != null && loop2 != null) {//大情况二:同时有环
            return bothLoop(head1, head2, loop1, loop2);
        }
        //大情况三：剩下一个有环和一个无环的情况，不可能有公共交点
        return null;
    }

    public Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
        //第一种是两个入环节点是同一个的情况
        if (loop1 == loop2) { //以入环节点为终点，然后按照noLoop中的情况处理
            int n = 0;
            Node n1 = head1;
            Node n2 = head2;
            while (n1 != loop1) {
                n1 = n1.next;
                n++;
            }
            while (n2 != loop1) {
                n2 = n2.next;
                n--;
            }
            n1 = n > 0 ? head1 : head2;
            n2 = n1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n1 = n1.next;
                n--;
            }
            while (n1 != n2) {
                n1 = n1.next;
                n2 = n2.next;
            }
            return n1;   //这个情况肯定有相交节点
        } else {
            Node n1 = loop1.next;
            while (n1 != loop1) {
                if (n1 == loop2) return loop2;
                n1 = n1.next;
            }
            return null;   //第三种是两个入环节点不是同一个的情况,但是拥有同一个环
        }

    }

    public Node noLoop(Node head1, Node head2) {
        int n = 0;
        Node n1 = head1;
        while (n1 != null) {
            n1 = n1.next;
            n++;
        }
        Node n2 = head2;
        while (n2 != null) {
            n2 = n2.next;
            n--;
        }
        if (n1 != n2) return null; //这个时候如果不是公共节点说明是两个不相交的链表
        n1 = n > 0 ? head1 : head2;
        n2 = n1 == head1 ? head2 : head1;
        //让head1变成长的那个链表
        n = Math.abs(n);
        while (n != 0) {
            n1 = n1.next;
            n--;
        }
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

    public Node getLoop(Node head) { //查看该链表是否有环
        if (head == null || head.next == null || head.next.next == null) return null;
        Node slow = head.next;
        Node 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 fast;
    }
复制代码