首页 > 其他分享 >【链表6】链表中环的入口结点

【链表6】链表中环的入口结点

时间:2022-11-22 12:31:31浏览次数:57  
标签:结点 indexNode1 ListNode val 中环 next 链表 pHead null


题目描述

一个链表中包含环,请找出该链表的环的入口结点。

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {

public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead == null)
return null;

ListNode slowNode=pHead;
ListNode fastNode=slowNode.next;

ListNode entryNode = null;//环中结点
//1 双指针,先获取环中任一结点
while(slowNode != null && fastNode!= null){
if(fastNode.val == slowNode.val){
entryNode = fastNode;
break;
}
fastNode = fastNode.next;
slowNode = slowNode.next;
if(fastNode != null)
fastNode=fastNode.next;
}

//判断此结点是否存在,不存在即不存在环
if(entryNode == null)
return null;

//2 获取环的长度
int lenOfCircleListNode =1;
ListNode indexNode1 =entryNode.next;
while(indexNode1 != entryNode){
lenOfCircleListNode++;
indexNode1 = indexNode1.next;
}

//3 双指针:让快指针先走(环长度)的步数,再两个指针一起走
//直到碰到第一个相同的数即为环的入口结点

//快指针
indexNode1 = pHead;
for(int i=0;i<lenOfCircleListNode;i++){
indexNode1 = indexNode1.next;
}
//慢指针
ListNode indexNode2 = pHead;
while( indexNode2 != null){
if(indexNode1.val == indexNode2.val){
return indexNode1;//返回入口节点
}
indexNode2 = indexNode2.next;
indexNode1 = indexNode1.next;
}
return indexNode2;



}
}


还有一种更加简便的方法:利用set特性

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
import java.util.*;


public class Solution {

public ListNode EntryNodeOfLoop(ListNode pHead)
{
Set<Integer> set = new HashSet<>();
//环的特点与集合的特性:环的入口结点即为遍历环时遇到的重复的结点
//而set集合不能添加重复结点.
//当添加重复结点时,set.add返回false,此时中断while循环,此时的结点phead即为环的入口节点
while(pHead != null && set.add(pHead.val)){
pHead = pHead.next;
}
return pHead;
}
}



标签:结点,indexNode1,ListNode,val,中环,next,链表,pHead,null
From: https://blog.51cto.com/u_15886477/5877697

相关文章

  • 【链表7】删除链表中重复的结点
    题目描述在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。例如,链表1->2->3->3->4->4->5处理后为1->2->5/*publicclass......
  • golang算法-链表逆序
    前言链表逆序,表述的场景为:A->B->C->D逆序后:D->C>B>A分析需要插入数据,Insert方法需要打印数据,Print方法插入数据时,需要定位最后一个节点,LastNode方法最少需要两个偏移量......
  • golang算法-判断链表是否有环
    前言链表有环,体现为:A->B->C->D->B…分析需要将遍历过的节点存入map,以址为key,空struct为值遍历时,当前节点是否已存在,存在即有环。实现链表//链表的长度,不包过头typeNode......
  • C/C++员工通讯录(链表实现)
    C/C++员工通讯录(链表实现)一、设计一个员工通讯录(如编号、身份证号码、姓名等),用单链表实现员工通讯录的存储和增删改查等操作。通讯录链表的建立;通讯者信息的插入;通讯......
  • 4.队列、栈、链表
    目录一、队列1.什么是队列2.抽象数据类型Queue3.python实现ADTQueue4.举例热土豆问题(约瑟夫问题)5.举例:打印队列二、双端队列1.什么是双端队列?2.抽象数据类型Deque3.pytho......
  • 【算法】Java解答有序链表转换二叉搜索树,从中序与后序遍历序列构造二叉树
    有序链表转换二叉搜索树给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点 19.删除链表的倒数第N个节点
     今日任务●24.两两交换链表中的节点●19.删除链表的倒数第N个节点●面试题02.07.链表相交●142.环形链表II●总结详细布置24.两两交换链表......
  • 代码随想录算法训练营第三天| 203.移除链表元素 707.设计链表 206.反转链表
    203.移除链表/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(in......
  • 有序单链表的合并
    有序单链表的合并将带表头的有序单链表La和Lb合并成Lc:structnode*merge(structnode*La,structnode*Lb){structnode*pa,*pb,*pc; //声明三个指针 pa=......
  • Java双向链表实现队列
    将双向链表做简单的改造,即可实现一个FIFO(FirstInputFirstOut)队列,该队列只在头节点出队,尾节点入队。一般来说定义节点类只需一个后驱节点next即可。这里保留pre节......