leetcode 141. 环形链表（链表是否有环）

缺乏、安全感 2022-02-26 13:16 297阅读 0赞

*  题目描述：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]
 *  分析：如果链表存在环，则遍历的时候永远会在这个环打转，如果不存在环则遍历到最后一个节点的下一个节点就是空的了，即是null。所以如果要判断一个链表是否存在环，则使用两个指针来遍历，一个慢指针一次走一格，一个快指针一次走两格，故如果存在环则在快的肯定会在环上撞见慢的，就跟人走路一样。具体实现如下：
    
        /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
        public class Solution { 
            public boolean hasCycle(ListNode head) { 
                if (head == null || head.next == null) { 
                    return false;
                }
                // 同一起点准备出发
                ListNode slowNode = head;
                ListNode fastNode = head;
                while (slowNode != null && fastNode != null) { 
                    // 慢的一次走一格
                    slowNode = slowNode.next; 
                    
                    // 快的一次走两格
                    fastNode = fastNode.next;
                    if (fastNode != null && fastNode.next != null) { 
                        fastNode = fastNode.next;
                    } else { 
                        return false;
                    }
                    
                    // 相遇：
                    // 慢的一次走一步，快的一次走两步，故如果不存在环，
                    // 则快的永远最先达到终点，期间不会与慢的相遇，
                    // 如果相遇了则肯定有环
                    if (fastNode != null && slowNode != null && fastNode==slowNode) { 
                        return true;
                    }
                }
                return false;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]: /images/20220226/6a49b739b4cf42dcb525f4ad12e4f847.png