当前位置:   article > 正文

算法32:环形链表(有双指针)_求环形链表的节点数java

求环形链表的节点数java

一、需求

给你一个链表的头节点 head ,判断链表中是否有环。

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

如果链表中存在环 ,则返回 true 。 否则,返回 false

示例 1:

在这里插入图片描述

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
  • 1
  • 2
  • 3

示例 2:

在这里插入图片描述

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
  • 1
  • 2
  • 3

示例 3:

在这里插入图片描述

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
  • 1
  • 2
  • 3

示例 4:

输入:head = [-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,14,2,13,-24,21,23,-21,5], pos = -1
输出:false
解释:链表中没有环,却有相同数,说明判断的是节点地址
  • 1
  • 2
  • 3

提示:

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos-1 或者链表中的一个 有效索引

**进阶:**你能用 O(1)(即,常量)内存解决此问题吗?

二、思路分析图

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

三、代码

(一)公共代码(链表类)

package com.bessky.pss.wzw.SuanFa;

import cn.hutool.core.util.StrUtil;

/**
 * 链表类
 *
 * @author 王子威
 * @date 2021/4/21
 */
public class ListNode
{
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString()
    {
        ListNode ln = this;
        StringBuilder sb = new StringBuilder();

        while(ln != null){
            if (StrUtil.isEmpty(sb))
            {
                sb.append("[" + ln.val);
            }
            else
            {
                sb.append("," + ln.val);
            }
            ln = ln.next;
        }
        sb.append("]");
        return sb.toString();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

(二)数据初始化/调用函数

/**
 * 入口
 *      141、环形链表
 * 输入:
 *      [3,2,0,-4]
 * 输出:
 *      true
 * 解释:
 *      1.快慢指针方案
 *      2.HashSet方案
 */
@Test
public void suanfa32()
{
    // 初始化
    ListNode one = new ListNode(3);
    ListNode two = new ListNode(2);
    ListNode three = new ListNode(0);
    ListNode four = new ListNode(4);
    one.next = two;
    one.next.next = three;
    one.next.next.next = four;
    one.next.next.next.next = two;

    // 打印
    boolean a = this.hasCycleSpeedPointer(one);
    System.out.println("快慢指针方案 = " + a);

    boolean b = this.hasCycleSet(one);
    System.out.println("HashSet方案 = " + b);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

(三)快慢指针方案

/**
 * 快慢指针方案
 *
 * @param head
 * @return
 */
private boolean hasCycleSpeedPointer(ListNode head)
{
    // 总结:只要有null就说明不是循环链表
    // 因为经过数学推算的公式:慢指针的速度为Vone  快指针的速度为Vtwo speedOne当前数S  speedTwo当前数F 间距N
    // 因终要 S - F = N
    // S + Vone - (F + Vtwo) = N - 1
    // S + Vone - F - Vtwo = N - 1
    // Vone - Vtwo = 1
    // 所以间距 = 1

    // 判断第一个或第二个节点为空
    if (head == null || head.next == null)
    {
        // 如果为空就说明不是环形链表返回false
        return false;
    }

    // 赋值到指针1中
    ListNode speedOne = head;
    // 赋值到指针2中,因为上面判空了,所以这里的head.next就不会因为节点只有一个而报错
    ListNode speedTwo = head.next;

    // 循环(指针1地址 不等于 指针2地址)只要相等就说明有环形链表
    while(speedOne != speedTwo)
    {
        // 因speedOne.next = speedTwo,这里不用判断了
        // 所以就判断speedTwo的后两个节点不为空既可
        if (speedTwo.next == null || speedTwo.next.next == null)
        {
            // 如果为空就说明不是环形链表返回false
            return false;
        }

        // speedOne赋值到下一个节点
        speedOne = speedOne.next;
        // speedTwo赋值到下一个节点的下一个节点
        speedTwo = speedTwo.next.next;
    }

    // 环形链表就返回true
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

(四)HashSet方案

/**
 * HashSet方案
 *
 * @param head
 * @return
 */
private boolean hasCycleSet(ListNode head)
{
    HashSet hash = new HashSet<>();
    while (head != null)
    {
        if (hash.contains(head))
        {
            return true;
        }
        hash.add(head);
        head = head.next;
    }
    return false;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

(五)结果图

在这里插入图片描述

作者:王子威

四、总结

  • 学习了环形链表

  • 因为上一个算法,这个直接就想到用HashSet做了

  • 总结:只要有null就说明不是循环链表
    // 因为经过数学推算的公式:慢指针的速度为Vone  快指针的速度为Vtwo speedOne当前数S  speedTwo当前数F 间距N
    // 因终要 S - F = N
    // S + Vone - (F + Vtwo) = N - 1
    // S + Vone - F - Vtwo = N - 1
    // Vone - Vtwo = 1
    // 所以间距 = 1
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
  • 快慢指针可以条件可以更改,就换一种写法了,不过都是对节点判空,值得注意的是因speedOne.next = speedTwo,这里不用判断speedOne了

  • 算法兴趣+1 总:32

  • 加强了对算法的分析能力

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/956988
推荐阅读
相关标签
  

闽ICP备14008679号