[数据结构与算法]07 关于单链表环的操作( Java 版)

红太狼 2023-06-25 10:21 5阅读 0赞

单链表经典操作,第一个是单链表反转,在这篇文章中已经写过了:[\[数据结构与算法\]04 Link List (链表)及单链表反转实现][04 Link List],第二个是判断链表中是否有环,也就是今天这篇文章想要说的.

# 判断链表是否有环 #

如图,我们能够清楚看到,这个链表是有环的.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70]  
咱们一起来分析一下

> 判断链表中是否有环,可以从头结点开始,依次遍历单链表中的每一个节点.每遍历一个节点,就和前面的所有节点作比较,如果发现新节点和之前的某个节点相同,则说明此节点被遍历过两次,说明链表有环,反之就是没有.

但是仔细看一下这种方法,你会发现这种方法很耗时耗力,因为每遍历一个节点,都要把它和前面所有的节点都比较一遍.  
还有一个很巧妙的方法,就是使用两个指针.

> 使用两个指针,一个快指针,一个慢指针.  
> 快指针每次走 2 步,慢指针每次走 1 步.  
> 如果链表中没有环,则快指针会先指向 null  
> 如果链表中有环,则快慢指针一定会相遇

基于这个思路,可以使用代码实现:

/** * 判断链表是否有环 * @author 郑璐璐 * @datetime 2019-12-28 09:44:41 */
    public class IsHasLoop { 
        public static class Node{ 
            private int data;
            private Node next;
            public Node(int data,Node next){ 
                this.data=data;
                this.next=next;
            }
            public int getData(){ 
                return data;
            }
        }
        public static void main(String[] args){ 
            // 初始化单链表
            Node node5=new Node(5,null);
            Node node4=new Node(4,node5);
            Node node3=new Node(3,node4);
            Node node2=new Node(2,node3);
            Node node1=new Node(1,node2);
            // 让 node5 的指针指向 node1 形成一个环
            node5.next=node1;
    
            boolean flag=isHasLoop(node1);
            System.out.println(flag);
    
        }
        public static boolean isHasLoop(Node list){ 
            if (list == null){ 
                return false;
            }
    
            Node slow=list;
            Node fast=list;
    
            while (fast.next != null && fast.next.next != null){ 
                // 慢指针走一步,快指针走两步
                slow=slow.next;
                fast=fast.next.next;
                // 如果快慢指针相遇,则说明链表中有环
                if (slow==fast){ 
                    return true;
                }
            }
    		// 反之链表中没有环
            return false;
        }
    }

#  求环长 #

现在已经将链表中是否有环判断出来了,接下来扩展一下,求环长.

先理一下整体思路:  
当快慢指针第一次相遇时,我们可以记录下此时的位置.  
接下来让慢指针继续走,每次走 1 步,直到走到第一次相遇的地方,此时慢指针走过的长度即为环长  
基于这样的思路,就可以将代码实现:

public static int getLength(Node list){ 
            // 定义环长初始值为 0
            int loopLength=0;
            Node slow=list;
            Node fast=list;
    
            while (fast != null && fast.next != null) { 
                // 慢指针走一步,快指针走两步
                slow=slow.next;
                fast=fast.next.next;
    
                // 第一次相遇时跳出循环
                if (slow == fast) break;
            }
            // 如果 fast next 指针首先指向 null 指针,说明该链表没有环,则环长为 0
            if(fast.next == null || fast.next.next == null){ 
                return 0;
            }
            // 如果有环,使用临时变量保存当前的链表
            Node temp = slow;
            // 让慢指针一直走,直到走到原来位置
            do{ 
                slow = slow.next;
                loopLength++;
            } while(slow != temp);
    
            return loopLength;
    }

# 求入环点 #

求入口节点有点儿绕,咱们先来上一张图:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70 1]  
如上图,假设:  
入环点距离头结点距离为 D  
入环点与首次相遇点较短的距离为 S1  
入环点与首次相遇点较长的距离为 S2

>  当两个指针首次相遇时,慢指针一次只走 1 步,则它所走的距离为: D+S1  
> 快指针每次走 2 步,多走了 n(n>=1) 圈,则它所走的距离为: D+S1+n(S1+S2)  
> 快指针速度为慢指针的 2 倍,则: 2(D+S1)=D+S1+n(S1+S2)  
> 上面等式,整理可得: D=(n-1)(S1+S2)+S2

如果让 (n-1)(S1+S2) 为 0 ,是不是 D 和 S2 就相等了?也就是说,当两个指针第一次相遇时,只要把其中一个指针放回到头结点位置,另外一个指针保持在首次相遇点,接下来两个指针每次都向前走 1 步,接下来这两个指针相遇时,就是要求的入环点.  
有点儿像做数学题的感觉~  
基于这样的思路,可以将代码实现:

public static Node entryNodeOfLoop(Node list){ 
            Node slow=list;
            Node fast=list;
            while(fast.next != null && fast.next.next != null){ 
                // 慢指针走一步,快指针走两步
                slow=slow.next;
                fast=fast.next.next;
    
                // 第一次相遇时跳出循环
                if (slow == fast) break;
            }
            // 如果 fast next 指针首先指向 null 指针,说明该链表没有环,则入环点为 null
            if (fast.next == null || fast.next.next == null){ 
                return  null;
            }
            // 第一次相遇之后,让一个指针指向头结点,另外一个指针在相遇位置
            // 两个指针每次走 1 步,相遇为止,此时相遇节点即为入环点
            Node head=list; // 头结点
            Node entryNode=slow;    // 相遇节点
            while (entryNode != head){ 
                entryNode=entryNode.next;
                head=head.next;
            }
            return entryNode;
    }

关于链表的一些操作差不多就是这些了.  
其实仔细观察能够看到,不管是求环长,还是找到入环点,最关键的是找到第一次相遇时所在的位置,基于这一点,接下来的问题就比较容易解决.

# 参考: #

*   漫画算法:小灰的算法之旅

以上,感谢您的阅读~

[04 Link List]: https://blog.csdn.net/zll_0405/article/details/103105533
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191228142025453.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191228211823177.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1,size_16,color_FFFFFF,t_70