链表的环问题（java）

た入场券 2023-03-14 10:33 39阅读 0赞

## 判断链表中是否有环 ##

问题概述：给定一个单链表，判断在此链表中是否存在环。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDUxOTIz_size_16_color_FFFFFF_t_70]

public class ListNode { 
        int val;
        ListNode next = null;
    
        ListNode(int val) { 
            this.val = val;
        }
        
    }

方法：使用快慢指针进行遍历

>     从头结点出发，快指针一次移动两个位置，慢指针一次移动一个位置。  
>    快指针的移动速度比慢指针速度快，所以如果存在环，则这两个指针一定会在环中的某一位置相遇，且**相遇时慢指针还未走完一圈**。如果不存在环，则快指针或慢指针会访问到链表的尾部（null结点）。

可以使用两种情况进行while循环的判断：

1. 使用设置`while(true)`条件，利用java的`try...catch..`机制，捕捉`NullPointerException`异常，如果存在该异常说明指针已达链表尾部，链表无环。如果在循环中找到快指针等于慢指针的情况，则链表存在环。

public static Boolean havingLoop(ListNode pHead){ 
            //设置快慢指针，快指针的移动速度是慢指针的两倍
            ListNode fast = pHead;
            ListNode slow = pHead;
            //如果存在环，则两指针必定相遇，不存在环，则快指针或慢指针可以访问到链表尾部
            try { 
                while (true){ 
                    slow = slow.next;
                    fast = fast.next.next;
                    if (slow == fast){ 
                        return true;
                    }
                }
            }catch (NullPointerException e){ 
                return false;
            }
    	}

2. 只需判断快指针是否访问到链表尾部结点即可。

public static Boolean havingLoop(ListNode pHead){ 
            //设置快慢指针，快指针的移动速度是慢指针的两倍
            ListNode fast = pHead;
            ListNode slow = pHead;
            //如果存在环，则两指针必定相遇，不存在环，则快指针或慢指针可以访问到链表尾部
            while (fast != null && fast.next != null){ 
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow){ 
                    return true;
                }
            }
            return false;
        }

## 找出环的入口点 ##

问题概述：给定一个单链表，如果该单链表上存在环，找到环的入口结点。  
方法：使用快慢指针  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDUxOTIz_size_16_color_FFFFFF_t_70 1]

>     在存在环的情况下，由于快慢指针相遇时，慢指针还未走完一圈环。  
>     - 设慢指针走的距离为s，则快指针走的距离为2s  
>     - 设快慢指针相遇点距离环入口的距离为x  
>     - 设环入口与起点位置的距离为a  
>     - 设环的长度为r，在快指针与慢指针相遇时，快指针已经遍历了环n圈  
>     - 链表总长度为L  
> 则存在如下数学关系：  
>    s = x + a；……①  
>    2s = x +a + n \* r；……②  
>    r = L - a；……③
> 
> --------------------
> 
> 由①、②可得：a = n \* r - x；……④  
> 由③、④可得：a = （n -1）\* r - x + r = (n -1)\* r - x + (L - a) = (n -1) = (n - 1) \* r - (L - a - x);……⑤
> 
> --------------------
> 
> 由⑤可得：**从链表起点开始到入口点的距离a**与**快慢指针相遇处到入口点的距离**（非x段）相等。通过这个结论，可以得出：如果一个指针从起点head位置开始移动，一个指针从快慢指针相遇位置开始移动，那么他们会在入口处相遇。

public ListNode EntryNodeOfLoop(ListNode pHead) { 
            //先判断是否存在环
            ListNode fast,slow;
            fast = slow = pHead;
            while (fast != null && fast.next != null){ 
                //快指针移动两步，慢指针移动一步
                fast = fast.next.next;
                slow = slow.next;
                //当快慢指针相等时，说明链表中存在环
                if (slow == fast)   break;
            }
    
            if (fast == null || fast.next == null){ 
                return null;
            }
    
            //此时快慢指针的位置即为相遇位置
            //开始第二次遍历
            fast = pHead;
            while (fast != slow){ 
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }

## 求环的长度 ##

方法：在得到相遇位置后，可以让慢指针再开始移动，在移动的过程中记录移动的次数，当慢指针再次到达相遇位置时，移动的次数就是环的长度。

public static int getLoopLength(ListNode pHead){ 
            //先判断是否存在环
            ListNode fast,slow ;
            fast = slow = pHead;
            int length = 0;
            while (fast != null && fast.next != null){ 
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) break;
            }
            if (fast == null || fast.next == null){ 
                return length;
            }
            //让slow移动，由于这种写法，会少算自身的一个结点，所以在循环结束后还需要+1
            while (fast != slow.next){ 
                slow = slow.next;
                length++;
            }
            length +=1;
            return length;
        }

## 求链表长度 ##

方法：求链表长度可以看作是前几个问题的综合，可以分为几步进行处理：

1.  获取环的入口位置
2.  求得链表起点位置到入口位置的长度……①
3.  求得环的长度……②
4.  将①、②相加

--------------------

附：  
测试使用的数据结构：

ListNode node1 = new ListNode(1);
            ListNode node2 = new ListNode(2);
            ListNode node3 = new ListNode(3);
            ListNode node4 = new ListNode(4);
            ListNode node5 = new ListNode(5);
            ListNode node6 = new ListNode(6);
            ListNode node7 = new ListNode(7);
            ListNode node8 = new ListNode(8);
            ListNode node9 = new ListNode(9);
    
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;
            node5.next = node6;
            node6.next = node7;
            node7.next = node8;
            node8.next = node9;
            node9.next = node2;

文章参考：

*  https://www.cnblogs.com/yorkyang/p/10876604.html
 *  https://blog.csdn.net/qq\_36781505/article/details/91401474

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDUxOTIz_size_16_color_FFFFFF_t_70]: /images/20230312/d081325d312c4d2f9dc08d5e57a40c28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDUxOTIz_size_16_color_FFFFFF_t_70 1]: /images/20230312/446ef9172a1a40babab1ea7574695650.png