leetcode142. 环形链表 II（环的第一个节点），O(N)时间复杂度与O(1)空间复杂度

雨点打透心脏的1/2处 2022-02-26 13:35 128阅读 0赞

*  题目描述  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]

#### O(N)的时间复杂度和O(N)的空间复杂度 ####

*  分析：可以使用一个map来记录每个遍历过的节点，当遍历到一个之前遍历过的节点时（第一次出现这种情况），则说明链表存在环了且这个节点是环的第一个节点，实现如下：
    
        /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
        public class Solution { 
            public ListNode detectCycle(ListNode head) { 
                if (head == null || head.next == null) { 
                    return null;
                }
                
                // 记录每一个遍历过的节点
                Map<ListNode, Boolean> record = new HashMap<>();
                
                ListNode node = head;
                // 遍历直到遇到一个遍历过的节点，或者无环则到链表尾部
                while (node != null && record.get(node)==null) { 
                    record.put(node, true);
                    node = node.next;
                }
                return node;
            }
        }

#### O(N)的时间复杂度和O(1)的空间复杂度 ####

*  以上这个解法需要O(N)的时间复杂度和O(N)的空间复杂度，更好的解法是基于O(N)的时间复杂度和O(1)的空间复杂度，具体实现与分析如下：

1.  快慢指针找到第一个相遇节点，此时快指针走的路程是慢指针的两倍，这个是解题关键
2.  设置一下变量：a，b，c  
    a: 起点到环的起点的距离  
    b: 环的起点到快慢指针第一次相遇的点的距离  
    c：相遇点到链表尾部的距离（该尾部节点的下一个节点回到环的起点）  
    D：第一次相遇时，慢指针走过的距离
3.  构造方程式：  
    D = a + b，2D = a + b + c + b 得出：  
    a = c，故之后慢指针可以回到起点，快指针从相遇点以每次一步的速度走，当快慢指针再次相遇时则是环的起点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 1]
    
        /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
        public class Solution { 
            public ListNode detectCycle(ListNode head) { 
                if (head == null || head.next == null) { 
                    return null;
                }
                
                // 快慢指针早到第一个相遇节点，此时快指针走的路程是慢指针的两倍，这个是解题关键
                // 设置一下变量：a，b，c
                // a: 起点到环的起点的距离
                // b: 环的起点到快慢指针第一次相遇的点的距离
                // c：相遇点到链表尾部的距离（该尾部节点的下一个节点回到环的起点）
                // D：第一次相遇时，慢指针走过的距离
                // 构造方程式：
                // D = a + b，2D = a + b + c + b 得出：
                // a = c，故之后慢指针可以回到起点，快指针从相遇点以每次一步的速度走，当快慢指针再次相遇时则是环的起点。
                
                ListNode fastNode = head;
                ListNode slowNode = head;
                
                while (fastNode != null && slowNode != null) { 
                    slowNode = slowNode.next;
                    fastNode = fastNode.next;
                    
                    if (fastNode != null) { 
                        fastNode = fastNode.next;
                    } else { 
                        break;
                    }
                    
                    // 第一次相遇
                    if (slowNode != null && fastNode != null && slowNode==fastNode) { 
                        break;
                    }
                }
                
                // 不存在环
                if (fastNode == null || slowNode == null) { 
                    return null;
                }
                
                // 肯定存在环
                // 慢指针回到起点
                slowNode = head;
                // 可能刚好就是起点
                if (slowNode == fastNode) { 
                    return slowNode;
                }
                
                // 快慢指针同时以每次一步的速度前进
                while (slowNode != fastNode) { 
                    slowNode = slowNode.next;
                    fastNode = fastNode.next;
                    
                    if (slowNode == fastNode) { 
                        return slowNode;
                    }
                }
                
                return null;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]: /images/20220226/8d05f13e44134811b6b4640cceb8f621.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 1]: /images/20220226/3cb5ff535c2e48a89ae376d2cc3feb90.png