链表中环的检测

深碍√TFBOYSˉ_ 2022-04-12 09:00 196阅读 0赞

#### 链表中环的检测 ####

定义两个快慢指针 pFast 和 pSlow，pFast 每次走两步，pSlow 每次走一步，如果 pFast 在循环遍历后为 null，则链表中不存在环。如果 pFast 和 pSlow 相遇则链表中存在环，废话不多说，看代码吧：

package com.jiaobuchong.common.algorithm.linkedlist;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class DetectLoop { 
        public static void main(String[] args) { 
            int[] arr = { 12, 13, 14};
            int[] loopArr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
            DetectLoop linkedListDemo = new DetectLoop();
            Node head = linkedListDemo.buildLoopLinkedList(arr, loopArr);
            
            boolean detectFlag = linkedListDemo.detectLoop(head);
            System.out.println("detect loop: " + detectFlag);
        }
    
        private static class Node { 
            final Integer item;
            Node next;
    
            Node(Integer item, Node next) { 
                this.item = item;
                this.next = next;
            }
        }
    
        /** * 通过数组构造一个带有环的链表 * * @param arr * @return */
        public Node buildLoopLinkedList(int[] arr, int[] loopArr) { 
            Node head = new Node(arr[0], null);
            Node p = head;
            if (arr.length >= 2) { 
                for (int i = 1; i < arr.length; i++) { 
                    Node temp = new Node(arr[i], null);
                    p.next = temp;
                    p = temp;
                }
            }
    
            // 构造一个环形链表
            Node loopHead = new Node(loopArr[0], null);
            if (loopArr.length >= 2) { 
                Node q = loopHead;
                for (int i = 1; i < loopArr.length; i++) { 
                    Node temp = new Node(loopArr[i], null);
                    q.next = temp;
                    q = temp;
                }
                q.next = loopHead;
            }
            p.next = loopHead;
            return head;
        }
    
        /** * 检查是否存在环形链表 * * @param head * @return */
        public boolean detectLoop(Node head) { 
            Node pSlow = head, pFast = head;
            boolean detectFlag = false;
            // 只包含一个结点
            if (head.next == null) { 
                return false;
            }
    
            List<Integer> slowPassNodes = new ArrayList<>();
            List<Integer> fastPassNodes = new ArrayList<>();
    
            while (pFast != null && pFast.next != null) { 
                // 慢指针走一步
                pSlow = pSlow.next;
                // 快指针走两步
                pFast = pFast.next.next;
    
                if (pFast != null) { 
                    fastPassNodes.add(pFast.item);
                }
                slowPassNodes.add(pSlow.item);
    
                // 如果快慢指针相遇则证明有环
                if (pSlow == pFast) { 
                    detectFlag = true;
                    break;
                }
            }
            System.out.println("slow pointer traverse node list: " + slowPassNodes);
            System.out.println("fast pointer traverse node list: " + fastPassNodes);
            return detectFlag;
        }
    }

代码中构造了一个环形链表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9idWNob25n_size_16_color_FFFFFF_t_70]

为什么 pFast 和 pSlow 会相遇呢？

1.  快指针与慢指针之间差一步，此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇；
2.  快指针与慢指针之间差两步，此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况;
3.  快指针与慢指针之间差 N 步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差 `(N + 1 - 2) -> N - 1` 步，最后总会转化为情况一。所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。

参考：  
[为什么用快慢指针找链表的环，快指针和慢指针一定会相遇？][Link 1]  
[Cycle detection in linked list with the Hare and Tortoise approach][]

#### 找出有环链表中的起始结点 ####

引用 [Explain how finding cycle start node in cycle linked list work?  
][Explain how finding cycle start node in cycle linked list work_] 中一张图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9idWNob25n_size_16_color_FFFFFF_t_70 1]  
pSlow 走过的长度是 x + y，  
pFast 走过的长度是 (x + y + z) + y = x + 2y + z，  
pFast 的速度是 pSlow 的两倍，于是有：2(x+y) = x+2y+z => x+2y+z = 2x+2y => x=z，x 表示的就是链表非环部分的长度，将 pSlow 指针指向链表头结点，同时移动 pSlow 和 pFast 直至它们相遇时就是环的起始结点。

在相遇点（meeting-point）,让 pFast 指向头节点 head，让 pSlow 和 pFast 同时移动，直至 pSlow 和 pFast 相遇，pSlow 所经过的步数就是环的长度，再次相遇点也就是环的起始节点。

看代码：

public Node findCycleHead(Node head) { 
            Node pSlow = head, pFast = head;
            // 只包含一个结点
            if (head.next == null) { 
                return null;
            }
    
            while (pFast != null && pFast.next != null) { 
                pSlow = pSlow.next;
                pFast = pFast.next.next;
                if (pSlow == pFast) { 
                    break;
                }
            }
    
            // pFast 指向头结点
            pFast = head;
            int i = 0;
            while (pFast != pSlow) { 
                pFast = pFast.next;
                pSlow = pSlow.next;
                i++;
            }
            System.out.println("非环部分长度：" + i);
            return pFast;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9idWNob25n_size_16_color_FFFFFF_t_70]: /images/20220412/7286920338f643849420936987b66365.png
[Link 1]: https://www.zhihu.com/question/23208893
[Cycle detection in linked list with the Hare and Tortoise approach]: https://stackoverflow.com/questions/6482886/cycle-detection-in-linked-list-with-the-hare-and-tortoise-approach?noredirect=1&lq=1
[Explain how finding cycle start node in cycle linked list work_]: https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9idWNob25n_size_16_color_FFFFFF_t_70 1]: /images/20220412/96316eb94c114a9db5e4da210b4d6bc2.png