【算法学习系列】java语言单链表的相交问题

傷城~ 2023-06-19 06:57 3阅读 0赞

#### 题目引入：如果两个单链表相交，则返回他们相交的第一个节点。 ####

##### 算法分析：该问题其实包含的情况很复杂，我们一步步来分析。 #####

1.  首先应该结合单链表的结构，一个值域，一个指针域，当两个单链表相交时，有以下几种情况。
2.  无环状态下的两种情况，一种是在某个节点相交，然后后面的链全部共有，第二种是两条链没有任何交集，第三种情况是不会出现的，因为违背了链表中节点只有一个指针的定义。  
    ![无环状态下][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70]
3.  有环状态下的链表相交，包含三种情况：  
    ![有环情况下的相交][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 1]
4.  以下就针对无环和有环条件下的链表相交进行讨论。

#### 1 判断链表有无环的存在，如果有返回环路的第一个节点，如果没有，就返回空指针。 ####

##### 1.1.1 使用HashSet的思想： #####

> 由于HashSet的无重性，构建一个Set对象，依次遍历单链表，如果遍历过程中发现了某节点已经在Set集合中了，那么该节点就是一个有环的链表，返回该节点。

##### 1.1.2 相关代码： #####

//判断是否有环，因为是单链表 当有环的时候 最后一个节点的next应该不为空
    //head 为链表的头节点或者第一个节点
        public Node getFirstLoopNode1(Node head){ 
            //声明一个hashSet进行检测
            HashSet<Node> set=new HashSet<Node>();
            while(head!=null){ 
                if(set.contains(head)){ 
                    return head;
                }
                set.add(head);//哈希set里面存的是内存地址
                head=head.next;
            }
            for(Node node:set){ 
                System.out.println("set val:"+node.value);
            }
            return null;
        }

##### 1.2 不使用HashSet的方式 #####

##### 1.2.1 算法思想： #####

> 这里会用到一个数学推论，即声明两个快慢指针，快指针(fast)一次走两步，慢指针(slow)一次走一步，如果快指针到了最后一个节点为 null 则说明该链表无环，返回null；如果fast和slow指针在某处相遇了，则说明链表一定有环，则再令快指针(fast)指向表的第一个节点，与慢指针同步遍历，最后快慢指针再次相遇的地方即是环路的第一个节点。  
> ![指针移动][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 2]  
> ![有环时候][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 3]

##### 1.2.2 代码实现： #####

public Node getFirstLoopNode3(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;
        }

#### 2 在判断完链表是否有环之后，就是分链表有环、无环两种情况，进行判断两者相交的第一个节点。 ####

##### 2.1 无环条件下 #####

###### 2.1.1 借助HashSet进行判断 ######

###### 算法思想： ######

> 将链表1的节点放进HashSet中，再将链表2的节点依次遍历，并判断是否在Set中存在，如果有则两者相交的第一个节点就是该节点，直接返回，满足博文之初那个无环相交的情况。

###### 2.1.2 相关代码： ######

//借助hashSet进行得到相交的第一个节点
        public Node getNoLoopLinkSet(Node head1,Node head2){ 
            if(head1==null || head2==null){ 
                return null;
            }
            HashSet<Node> set=new HashSet<Node>();
            this.helpNode=head1;
            while(this.helpNode!=null){ 
                set.add(this.helpNode);
                this.helpNode=this.helpNode.next;
            }
            this.helpNode=head2;
            while(this.helpNode!=null){ 
                if(set.contains(this.helpNode)){ 
                    return this.helpNode;
                }
                this.helpNode=this.helpNode.next;
            }
            return null;
        }

###### 2.2 不借助 HashSet 进行判断无环相交的第一个节点 ######

###### 2.2.1 算法思想： ######

> 首先，判断两链表是否有共同的尾节点，如果有，则说明两链表相交；如果没有，则说明两链表不相交，直接返回。当判断为两链表相交后，需要通过移动链表的方式进行得到两者相交的第一个节点，这就涉及到链表长度的问题，如果两者长度不同，假设一个长度 L1，另一个L2，如果L1>L2,则让链表1先移动(L1-L2)的长度，然后再和第二个链表同步移动指针，当他们在某个节点相同时，就是相交的第一个节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 4]

##### 2.2.2 代码实现 #####

//不借助单链表进行得到两相交链表的第一个节点
        public Node getNoLoopFirstNode(Node head1,Node head2){ 
            if(head1==null || head2==null){ 
                return null;
            }
            int n=0;//记录两个链表的差
            Node cur1=head1;
            Node cur2=head2;
            while(cur1!=null){ 
                n++;//得到 链表1 的长度
                cur1=cur1.next;
            }
            while(cur2!=null){ 
                n--;//得到 链表1与2 的差
                cur2=cur2.next;
            }
            cur1=n > 0 ? head1:head2; //n大于0则 1 链表长度 > 2 链表长度
            cur2=cur1==head1 ? head2:head1;
            while(n>0 && n!=0){ 
                cur1=cur1.next;
                n--;
            }
            while(n<0 && n!=0){ 
                cur1=cur1.next;
                n++;
            }
            while(cur1!=cur2){ 
                cur1=cur1.next;
                cur2=cur2.next;
            }
            return cur1;
        }

#### 3 在有环条件下判断相交，且返回相交的第一个节点。 ####

##### 3.1 有环时相交与否满足以下几种情况 #####

1.  A B各为单个的有环链路，不相交
2.  A B相交在环路之前
3.  A B相交在环上，但可能点不一样

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 5]

##### 3.2 针对以上三种结构，算法思想如下 #####

1.  遍历A B链表，返回有环的第一个节点 loop1 和 loop2
2.  如果loop1==loop2 则为上图的相交的情况（第二幅图），将loop1 或 loop2作为链表的尾，从头开始遍历直到找到第一个相交的点。返回即可。
3.  如果 loop1 != loop2 则为 第一种情况或者第三种，这种情况下，就是从loop1 开始遍历，终止条件为 再次返回到 loop1 ，看看这期间有没有遇到 loop2 如果有，则返回 loop1 或者 loop2即为两链表相遇的节点，如果没有，就是两链表没有相交，返回null.

##### 3.3 代码实现 #####

public Node getLoopFirstNode(Node head1,Node head2){ 
            if(head1==null || head2==null){ 
                return null;
            }
            System.out.println("begin test.."+noLoopLink(head1)+" "+noLoopLink(head2));
            //判断两链表均有环
            if(!noLoopLink(head1) && !noLoopLink(head2)){ 
                Node loop1=getFirstLoopNode3(head1);
                Node loop2=getFirstLoopNode3(head2);
                Node cur1=null;
                Node cur2=null;
                int n=0;//找两链表长度的差值
                if(loop1==loop2){ 
                    cur1=head1;
                    cur2=head2;
                    while(cur1!=loop1){ 
                        n++;
                        cur1=cur1.next;
                    }
                    while(cur2!=loop2){ 
                        n--;
                        cur2=cur2.next;
                    }
                    cur1=n > 0?head1:head2;
                    cur2=cur1==head1?head2:head1;
                    n=Math.abs(n);//取绝对值
                    while(n!=0){ 
                        cur1=cur1.next;
                        n--;
                    }
                    //可以使用 n 取绝对值来实现不用判断的过程
                   /* while(n>0 && n!=0){ cur1=cur1.next; n--; } while(n<0 && n!=0){ cur1=cur1.next; n++; }*/
                    //System.out.println("the cur1:"+cur1.value+" "+cur2.value);
                    while(cur1!=cur2){ 
                        cur1=cur1.next;
                        cur2=cur2.next;
                    }
                    return cur1;
                }else{ 
                    cur1=loop1.next;
                   // cur2=loop1;
                    while(cur1!=null && cur1!=loop1){ 
                        cur1=cur1.next;
                    }
                    return null;
                }
    
            }
            System.out.println("the link has no cycle..");
           return null;
        }

以上为判断单链表相交的内容，如果有问题，欢迎指正！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019120509011171.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191205090623247.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191205092540202.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191205092954697.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191205095106250.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191205095350490.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NzUwNDYx,size_16,color_FFFFFF,t_70