赞
踩
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
输入: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
解释:链表中没有环,却有相同数,说明判断的是节点地址
[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();
}
}
/**
* 入口
* 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);
}
/**
* 快慢指针方案
*
* @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;
}
/**
* 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;
}
作者:王子威
学习了环形链表
因为上一个算法,这个直接就想到用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
快慢指针可以条件可以更改,就换一种写法了,不过都是对节点判空,值得注意的是因speedOne.next = speedTwo,这里不用判断speedOne了
算法兴趣+1 总:32
加强了对算法的分析能力
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。