前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Q142 环形链表 II(Linked List Cycle II)

Q142 环形链表 II(Linked List Cycle II)

作者头像
用户2038589
发布2022-05-11 11:04:07
2080
发布2022-05-11 11:04:07
举报
文章被收录于专栏:青青天空树

解析思路

  leetcode 中等难度,题目描述点击这里

  看到题目描述首先蹦出来的解法就是遍历链表,记录走过的节点,当某个节点第二次走到的时候说明该节点就是环的起点,当节点没有下个节点说明没有环。本方法很简单不做详细说明,用一个HashSet记录访问过的节点即可。

  有没有更好的版本呢?当然是有的。通常使用快慢指针的办法来解决这类链表环的问题。思路如下:

  1. 定义两个指针slow(慢指针,每次走1个),fast(快指针,每次走两个),都从head出发。
  2. 每进行一次移动fast和slow间隔的节点就会+1,由此可以推断当slow进入环后,一定会和fast相遇
  3. 假设链表非环的长度为a,环的长度为b,fast走过的距离为f,slow走过的距离为s,当fast在环中循环n次后,fast,slow首次相遇,可得到如下表达式: f=2s(f的速度是s的两倍) f=s+nb(一定比s走的距离多n圈才会相遇) 由上面两个得到:s=nb,由于s走的距离肯定包含了a,可以得到s在环中走的距离为nb-a,只需要继续走a的距离就能刚好走到环的起点。
  4. 所以再加一个指针c从head开始,每次移动一格,当c和slow相遇时说明到了环的起点

java如下:

代码语言:javascript
复制
package com.fanxb.common;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 环形链表 II
 * 题目地址:https://leetcode-cn.com/problems/linked-list-cycle-ii/
 * 解题思路:
 *   解法1:只要找到是否某个节点访问了两次即可,用set记录已访问过的节点,当访问的节点在set中说明找到了环形链表头,当节点没有下一个节点说明不存在环
 *   更优化的解法2:
 *     使用快慢指针,定义两个指针slow(慢指针,每次走1个),fast(快指针,每次走两个),都从head出发。
 *     每进行一次移动fast和slow间隔的节点就会+1,由此可以推断当slow进入环后,一定会和fast相遇
 *     假设链表非环的长度为a,环的长度为b,fast走过的距离为f,slow走过的距离为s,当fast在环中循环n次后,fast,slow首次相遇,可得到如下表达式:
 *     f=2s(f的速度是s的两倍)
 *     f=s+nb(一定比s走的距离多n圈才会相遇)
 *     由上面两个得到:s=nb,由于s走的距离肯定包含了a,可以得到s在环中走的距离为nb-a,只需要继续走a的距离就能刚好走到环的起点。
 *     所以再加一个指针c从head开始,每次移动一格,当c和slow相遇时说明到了环的起点
 *
 * @author fanxb
 * Date: 2020/6/9 15:10
 */
public class Q142 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static ListNode solution(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            } else {
                set.add(head);
                head = head.next;
            }
        }
        return null;
    }

    public static ListNode betterSolution(ListNode head) {
        ListNode slow = head, fast = head;
        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
        //此时快慢指针相遇,再加一个指针c
        ListNode c = head;
        while (c != slow) {
            slow = slow.next;
            c = c.next;
        }
        return c;
    }

}

本体存在一些变体也是一样的解法,

比如找到开始节点后的第n个节点,可在找到头后再遍历n次

比如找到开始节点前的第n个节点,一样的找到头后,再遍历一遍环得到环长度,再计算出需要遍历的次数,得到距离开始节点前的第n个节点

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-03-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解析思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档