Day8 25/2/21 FRI

【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358

目录

4、链表

4.3.4 例4 两个单链表相交

解法1：存set

解法2：快慢指针

情况1：都无环

（1-1）哈希表。

（1-2）仅用有限几个变量

情况2：一个有环一个无环

情况3：两个都有环

主函数的调用

笔记：

4、链表

4.3.4 例4 两个单链表相交

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

【要求】如果量链表长度之和为N，时间复杂度要达到O(N)、额外空间复杂度要达到O(1)。

两链表相交，即两表各自有一个节点的内存地址相同。

解法1：存set

遍历链表然后把节点存入set，在set李第二次遇到相同节点时，该节点就是入环的第一个节点

解法2：快慢指针

这个方法无需调用额外的数据结构。

单链表如果有环的话，不会出现下图的状况。因为如果有环且环之后还留有拖尾，则会导致交点处有两个next指针，而这在单链中不会存在。

如果单链中有环，只会如下图所示。

遍历单链时，一旦最终走到了null，则说明没有环。有环的话最终一定走到入环的第一个节点处。

首先，快指针F每次走两步、慢指针S每次走一步，如果有环的话它俩必然在环内某个节点相遇。

然后慢指针S停留在原地，快指针F返回单链的开头，两个指针每次都各走一步，它们最终一定会在入环的第一个节点相遇。

解释：F走的步数是S的两倍，F与S的步差值是环的n倍，所以F和S都走了环的整数倍。再走环外的步数都会走到环起始点，因此相遇。

public static Node getLoopNode(Node head){
    if(head == null || head.next == null || head.mext.next == null{
        return null;
    }
    Node slowP = head.next;  //慢指针一次走一格
    Node fastP = head.next.next;  //快指针一次走两格
    while( slowP != fastP){
        if(fastP.next == null || fastP.next.next = null){
            return null;  //也就是单链上无环
        }

        fastP = fastP.next.next;
        slowP = slowP.next;
    }
    fastP = head;  //代码走到这步，说明单链上有环，于是快指针返回到单链的头，然后继续找入环的第一个节点
    while(fastP != slowP){
        fastP = fastP.next;
        slowP = slowP.next;
    }
    return slowP;
}

现在继续看两个链表的相交问题。

用上面的函数分别运行两个单链表，得到的入环节点的返回值可能有：

情况1：都无环

loop1 == null 且 loop2 == null

解释：两条单链不相交。由于各自都是单链，节点到节点之间只有一个next指针，所以不可能出现下图的情况。下图的相交节点处会出现往左和往右的两个next指针，因此不成立。

如果两条单链相交且没有环，则说明两条单链交点之后的部分一定是公共部分，类似下图。

找到情况1的相交节点，有两种方法。

（1-1）哈希表。

用哈希表记录一条链的节点，然后边遍历另一条链边检查节点是否在哈希表中。

（1-2）仅用有限几个变量

用需要分别从头到尾遍历单链1和单链2，并各自记录链的长度len1、len2（也可以像下面代码中用一个变量len，遍历单链1是len++，遍历单链2时len—）。然后让链更长的那条先走| len1-len2 |步，然后另一条从头开始走，这样它们必然在第一个相交节点处相遇，如同对齐然后拉上拉链一样。

public static Node noLoop(Node head1, Node head2){
    if(head1 == null || head2 == null){
        return null;
    }
    Node cur1 = head1;
    Node cur2 = head2;
    int len = 0;
    while(cur1.next != null){
        len++;   //遍历计算单链1的长度
        cur1 = cur1.next;
    }
    while(cur2.next != null){
        len--;   //遍历完单链2之后，len的数值就是单链1和2的长度差值
        cur2 = cur2.next;
    }
    if( cur1 != cur2) return null;  //两个单链最终没有汇合在同一个尾部的情况（需要排除）
    if( n > 0 ){ //单链1长度>单链2
        cur1 = head1;   //此时cur1等于更长的那条链的头部
        cur2 = head2
    }else{  //单链1长度<=单链2
        cur1 = head2;    //此时cur1等于更长的那条链的头部
        cur2 = head1;
    }
    n = Math.abs(n);  //让长的那条链先走完n步
    while( n !=0 ){
        n--;
        cur1 = cur1.next;
    }
    while( cur1 !=cur2 ){  //两条里一起遍历，找到第一个相交节点
        cur1 = cur1.next;
        cur2 = cur2.next; 
    }
    return cur1;
}

情况2：一个有环一个无环

两单链此时不可能相交。

情况3：两个都有环

loop1 != null且loop2 != null

情况3共有三种不同处境：

（3-1）不相交且入环节点也不同；（3-2）相交且交点在环之前；（3-3）相交且入环节点不同

对于（3-2）的情况，可参考上面（1-2）的相交且无环的代码。

区分（3-1）和（3-3），只需要让一个单链1走入环后停止并记录当前节点，单链2在环里继续走，看在环中转的时候单链2是否能遇到单链1的那个节点即可。

能遇到则是（3-3），返回单链1或单链2的第一个入环节点都可以。遇不到则是（3-1），第一个入环节点为null。

public static void bothLoop(Node head1, Node loop1, Node head2, Node loop2){
    Node cur1 = null;
    Node cur2 = null;
    if(loop1 == loop2){  //这部分就是（1-2）的代码
        cur1 = head1;
        cur2 = head2;
        int len = 0;
        while(cur1 != loop1){
            len++;   //遍历计算单链1的长度
            cur1 = cur1.next;
        }
        while(cur2 != lopp2){
            len--;   //遍历完单链2之后，len的数值就是单链1和2的长度差值
            cur2 = cur2.next;
        }
        if( n > 0 ){ //单链1长度>单链2
            cur1 = head1;   //此时cur1等于更长的那条链的头部
            cur2 = head2;
        }else{  //单链1长度<=单链2
            cur1 = head2;    //此时cur1等于更长的那条链的头部
            cur2 = head1;
        }
        n = Math.abs(n);  //让长的那条链先走完n步
        while( n !=0 ){
            n--;
            cur1 = cur1.next;
        }
        while( cur1 !=cur2 ){  //两条里一起遍历，找到第一个相交节点
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
    }else{
        cur1 = loop.next;
        while(cur1 != loop1){  //cur1一直走，在回到loop1这个节点之前如果遇到了loop2，就是（3-3）的情况，否则就是（3-1）的情况
            if(cur1 == loop2){
                return loop1;
            }
            cur1 = cur1.next
        }
    return null;
    }
}

主函数的调用

public static Node getIntersectNode(Node head1, Node head2){
    if(head1 == null || head2 == null){
        return null;
    }
    Node loop1 = getLoopNode(head1);     //getLoopNode()：找到链表第一个入环节点，如果无环则返回null
    Node loop2 = getLoopNode(head2);
    if(loop1 == null && loop2 == null){  //情况1
        return noLoop(head1, head2);
    }
    if(loop1 != null && loop2 != null){  //情况3
        return bothLoop(head1, loop1, head2, loop2);
    }
    return null;  //情况2
}