【Leetcode 程序员面试金典 02.08】 —— 环路检测 |双指针

简介: 我们可以使用双指针解决本题,由数学推导可知:a 的距离为(环长度的倍数 - b),即 tmp 指针从头节点走到环开头节点等于 slow 指针走到环开头节点的距离

面试题02.08. 环路检测

给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回null

如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果pos-1,则在该链表中没有环。注意:pos不作为参数进行传递,仅仅是为了标识链表的实际情况。

题目分析

我们可以使用双指针解决本题

快指针走了:$a + (b+c)m + b$
慢指针走了:$a + (b+c)n + b$
根据快走的是慢的两倍,
$a + (b+c)m + b = 2(a + (b+c)n + b)$ =>
$a = (b+c)(m-2n) - b$

得 a 的距离为(环长度的倍数 - b),即 tmp 指针从头节点走到环开头节点等于 slow 指针走到环开头节点的距离

双指针顾名思义,就是同时使用两个指针,在序列、链表结构上指向的是位置,在树、图结构中指向的是节点,通过或同向移动,或相向移动来维护、统计信息

经典双指针的数组遍历,更多案例可见 Leetcode 双指针详解

/**
 * 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){
   
   
            return null;
        }

        ListNode slow = head, fast = head;
        while(fast != null){
   
   
            slow = slow.next;
            if(fast.next != null){
   
   
                fast = fast.next.next;
            } else {
   
   
                return null;
            }

            if(slow == fast){
   
   
                ListNode tmp = head;
                while(tmp != slow){
   
   
                    tmp = tmp.next;
                    slow = slow.next;
                }
                return tmp;
            }
        }
        return null;
    }
}
相关文章
|
1月前
|
算法
LeetCode刷题---21.合并两个有序链表(双指针)
LeetCode刷题---21.合并两个有序链表(双指针)
|
1月前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
1月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
1月前
|
存储 容器
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
|
1月前
|
算法
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
|
1月前
|
存储 算法
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
|
1月前
|
算法
LeetCode刷题---283. 移动零(双指针)
LeetCode刷题---283. 移动零(双指针)
|
21天前
|
算法
【力扣经典面试题】121. 买卖股票的最佳时机
【力扣经典面试题】121. 买卖股票的最佳时机
|
21天前
|
存储
【力扣经典面试题】80. 删除有序数组中的重复项 II
【力扣经典面试题】80. 删除有序数组中的重复项 II
|
1月前
|
编解码 缓存 安全
【C/C++ 泡沫精选面试题03】谈谈C/C++ 智能指针?
【C/C++ 泡沫精选面试题03】谈谈C/C++ 智能指针?
31 1

热门文章

最新文章