首页 > 其他 > 详细

142. 环形链表 II + 快慢指针 + Set

时间:2021-03-04 23:16:25      阅读:6      评论:0      收藏:0      [点我收藏+]

142. 环形链表 II

LeetCode_142

题目描述

技术分享图片

题解分析

  1. 判断链表是否存在环
  • 对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow,开始的时候两个指针都指向链表头head,然后在每一步操作中slow向前走一步即:slow = slow->next,而fast每一步向前两步即:fast = fast->next->next。由于fast要比slow移动的快,如果有环,fast一定会先进入环,而slow后进入环。当两个指针都进入环之后,经过一定步的操作之后二者一定能够在环上相遇,并且此时slow还没有绕环一圈,也就是说一定是在slow走完第一圈之前相遇。
  1. 寻找链表中环的起点

    • 从链表起点head开始到入口点的距离a,与从slow和fast的相遇点(如图)到入口点的距离相等。
    • 我们就可以分别用一个指针(ptr1, prt2),同时从head与slow和fast的相遇点出发,每一次操作走一步,直到ptr1 == ptr2,此时的位置也就是入口点!
  2. 计算链表中环的结点个数

    • 从相遇点开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next;直到二者再次相遇,此时经过的步数就是环上节点的个数 。

代码详情

/**
 * 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) {
        ListNode slow = head, fast = head;
        while(fast != null){
            if(fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
            //slow还没有走完一圈快慢指针必定会相遇
            if(fast == slow){
                ListNode now = head;
                //从相遇的地方再次循环
                while(now != slow){
                    slow = slow.next;
                    now = now.next;
                }
                return now;
            }
        }
        return null;
    }
}

142. 环形链表 II + 快慢指针 + Set

原文:https://www.cnblogs.com/GarrettWale/p/14483240.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号