精华内容
下载资源
问答
  • 题目描述:给定一个链表,返回链表开始入环的第一个节点. 如果链表,则返回null.为了表示给定链表中的,我们使用整形pos来 表示链表尾连接到链表中的位置(索引从0开始).如果pos是-1,则在该链 表中没有.注意,pos...
    /*
    leetCode142
    题目描述:给定一个链表,返回链表开始入环的第一个节点.
    如果链表无环,则返回null.为了表示给定链表中的环,我们使用整形pos来
    表示链表尾连接到链表中的位置(索引从0开始).如果pos是-1,则在该链
    表中没有环.注意,pos仅仅是用于标识环的情况,并不会作为参数传递到函数中.
    说明:不允许修改给定的链表。
    
    示例 1:
    输入:head=[3,2,0,4],pos=1
    输出:返回索引为1的链表节点
    解释:链表中有一个环,其尾部连接到第二个节点;
    
    示例 2:
    输入:head=[1,2],pos=0
    输出:返回索引为0的链表节点
    解释:链表中有一个环其尾部连接到第一位节点;
    
    示例 3:
    输入:head=[1],pos=-1
    输出:返回null
    解释:链表中没有环;
    
    解题思路:
    利用双指针,一个慢指针S、一个快指针F(2S),设置入环前距离为a,慢指针
    入环后走过的距离为b,环剩余距离为c,其中b+c代表一个环.
    首次相遇:
    (1)慢指针走过的路程:S=a+b;
    (2)快指针走过的路程:F=a+n(b+c)+b,其中n>=1,快指针起码在环中走
    了一圈以上才可能相遇;
    (3)快指针走二步,慢指针走一步,即F=2S;
    (4)因此2(a+b)=a+n(b+c)+b,所以a=(n-1)(b+c)+c;
    (5)其中n为快指针绕的圈数,当n=1,a=c;当n=2,a=一圈+c;当n=3,
    a=两圈+c....所以c为入环点,就是所求的索引点;
    */

    Go语言实现 

    package main
    
    import "fmt"
    
    //创建节点结构/类型
    type Node struct{
    	Data interface{}
    	Next *Node
    }
    
    //创建链表结构
    type List struct{
    	Head *Node
    	Size int   //头节点不作为链表长度
    }
    
    //设计接口
    type Method interface {
    	Insert(i int,v interface{})
    	IsNull() bool
    	GetSize() int
    	Print()
    	SetCycle(n int)
    	detectCycle() interface{}
    }
    
    //创建节点
    func CreateNode(v interface{} ) *Node{
    	return &Node{v,nil}
    }
    
    //创建空链表
    func CreateList() *List{
    	return &List{CreateNode(nil),0}
    }
    
    //基于Method接口实现链表结构体
    //在i处插入节点
    func (list *List) Insert(i int,v interface{}){
    	s:=CreateNode(v)
    	pre:=list.Head //头节点
    	for count:=0;count<=i;count++{
    		if count==i-1{
    			s.Next=pre.Next
    			pre.Next=s
    			list.Size++  //前插法
    		}
    		pre=pre.Next
    	}
    }
    
    //判读是否为空
    func (list *List) IsNull() bool{
    	pre:=list.Head.Next
    	if pre==nil{
    		return true
    	}
    	return false
    }
    
    //返回链表长度
    func (list *List) GetSize() int{
    	return list.Size
    }
    
    //设计链表打印输出
    func (list *List)Print(){
    	pre:=list.Head.Next
    	fmt.Println("链表:")
    	for i:=1;i<=list.Size;i++{
    		fmt.Printf("%v -> ", pre.Data)
    		pre=pre.Next
    	}
    }
    
    //设置环入口的索引点
    func (list* List)SetCycle(n int){
    	temp,last:=list.Head.Next,list.Head.Next
    	for i:=1;i<n;i++{
    		temp=temp.Next
    	}
    	for i:=1;i<list.Size;i++{
    		last=last.Next
    	}
    	/*尾部节点指向索引节点*/
    	last.Next=temp
    }
    func (list* List)detectCycle()interface{}{
    	fast,slow:=list.Head.Next,list.Head.Next
    
    	/*首次相遇时,slow的位置*/
    	for fast!=nil&&fast.Next!=nil{
    		fast=fast.Next.Next
    		slow=slow.Next
    		if slow==fast{
    			break
    		}
    	}
    
    	/*如果快指针走到尽头,没环*/
    	for fast==nil||fast.Next==nil{
    		return -1
    	}
    
    	/*快指针重新出发,相遇位置就是入口的位置*/
    	fast=list.Head.Next
    	for fast!=slow{
    		fast=fast.Next
    		slow=slow.Next
    	}
    	return slow.Data
    }
    
    func main() {
    	fmt.Println("链表开始入环的第一个节点")
    	list := CreateList()
    	var m Method //或者var m Method=CreateList()
    	m = list
    	m.Insert(1, 3)
    	m.Insert(2, 7)
    	m.Insert(3, 8)
    	m.Insert(4, 10)
    	m.SetCycle(3)
    	m.Print()
    	fmt.Println(m.detectCycle())
    }

     

    展开全文
  • js代码-寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常...
  • js代码-FindFirstNodeJS 寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常...
  • java代码-寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 Id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常...
  • 寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 id。现在请实现一个办法寻找该链表的头节点。 PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印异常消息即可。
  • 返回链表入环节点

    2021-03-06 14:56:58
    从两个快慢指针交汇的地方到入环节点的距离和从链表第一个节点到入环节点的距离是相同的 创建两个引用cur1,cur2,分别指向链表的第一个节点和快慢指针交汇的地方,两个引用重合的地方便是链表环节点 代码 ...

    思路

    • 首先判断链表是否存在环,如果不存在直接返回null(快慢指针判断链表是否有环博客链接
    • 从两个快慢指针交汇的地方到入环节点的距离和从链表第一个节点到入环节点的距离是相同的

    • 创建两个引用cur1,cur2,分别指向链表的第一个节点和快慢指针交汇的地方,两个引用重合的地方便是链表的入环节点

    代码

    public class Solution11 {
        public ListNode detectCycle(ListNode head) {
            if(head==null||head.next==null){
                return null;
            }
            //快慢指针判断链表中是否存在环
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
                    break;
                }
            }
            if(fast==null||fast.next==null){
                //说明链表是不带环的
                return null;
            }
            ListNode cur1=head;
            ListNode cur2=fast;
            while(cur1!=cur2){
                cur1=cur1.next;
                cur2=cur2.next;
            }
            return cur1;
        }
    }
    

     

    展开全文
  • 例题 leetcode中的例题 思路 如果只是判断一个链表是否成环,我们常用的是快慢指针。...设根(a) 到起点的距离为x,起点(b)到链表尾部(d)的距离为y。快慢指针相遇的点(c)距离起点的距离为r。 根据快慢指针相遇

    例题

    leetcode中的例题

    思路

    • 如果只是判断一个链表是否成环,我们常用的是快慢指针。即让一个指针一次迈一步,另一个指针一次迈两步。如果链路承欢,则两个指针最终是会相遇的。

    但是 怎么在这个基础上找到环路的开始节点呢。

    我们可以再跑一次,这次同步伐(都走一步),一个从头开始,一个从快慢指针相遇的地方开始。这次的相遇即为目标节点(我们要找的环路开始节点) —这是floyd判圈算法(龟兔赛跑算法)

    证明如下:

    在这里插入图片描述
    设一圈长度为l,快慢指针追上时,m+n=m+kl+n => m+n=kl(快指针追上慢指针多跑了整数倍的圈数,k为某个正整数)。
    然后第二次追赶的时候,相遇即为入环的第一个节点:
    因为S到A需要m B到A的话由于是圈,可以反复跑,即l-n,2l-n,…
    当重复到kl-n时,才会再次相遇。

    代码如下

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode slow = head, fast = head;        
            //while 循环跳出条件是不成环
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                // 这里是用来跳出的,即为c点
                if (slow == fast) {
                    break;
                }
            }
            // 这里 是接不成环的情况的
            if (fast == null || fast.next == null) {
                return null;
            }
            //这里开始第二次的相遇。
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    

    当然了,上面的是好方法,稍微差一点的还有一个。

    • 我们可以从头开始遍历,把每次的节点都存到hashMap或者set中,一旦发现有重复,说明遇到环了,而且当前节点就是成环的开始节点。

    代码如下

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            Map<ListNode,Integer> map=new HashMap<ListNode,Integer>();
            while(head!=null){
                if(map.getOrDefault(head,0)==0){
                    map.put(head,1);
                }
                else{
                    return head;
                }
                head=head.next;
            }
            return null;
        }
    }
    

    参考

    Floyd判圈算法(龟兔赛跑算法, Floyd’s cycle detection)及其证明

    展开全文
  • java代码-*寻找链表的头节点,每个节点,有 id 和 nextId 两个属性,nextId 表示指向节点 Id。现在请实现一个办法寻找该链表的头节点。 * PS. 考虑一下链表环状,以及节点不在链表内等异常情况,出现异常时,打印...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null。 为了表示给定链表中的,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有。...

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    说明:不允许修改给定的链表。

    在这里插入图片描述
    解题思路:
    用数学思路,快慢指针在meetNode处是相交的结点,这时候可以计算出快慢指针之间的关系,慢指针走了L+X,快指针走了L+X+NC,2slow=fast;那么L=N*C-X,发现如果此时将meetNode和头指针重新同步遍历,最后相交结点就是环的入口结点。

    在这里插入图片描述

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    typedef struct ListNode Node;
    struct ListNode *detectCycle(struct ListNode *head) {
        Node* slow = head;
        Node* fast = head;
    
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
    
            if(slow == fast)
            {
                Node* meet = slow;
                Node* start = head;
    
                while(meet != start)
                {
                    meet = meet->next;
                    start = start->next;
                }
                return meet;
            }
        }
        return NULL;
    }
    
    展开全文
  • 给定一个链表,返回链表开始入环的第一个节点。如果链表,则返回NULL OJ链接 思路: 对于这样的一个带环链表进之前的长度为L,的长度为C,使用快慢指针,找到相遇的结点,结点位置距离的入口为K,则...
  • 判断判断出这个链表是否有?方法一:方法二:方法三:如果链表,如何求出的长度?...如果发现新节点之前的所有节点当中存在相同节点ID,则说明该节点被遍历过两次,链表; 如果之前的所有节点当中不存在
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null。 为了表示给定链表中的,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有。...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null。 为了表示给定链表中的,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有。...
  • 这个链表返回第三个结点,如果无,返回null。 2.问题分析 这道题需要设置两个指针,一个快,一个慢,快指针走两步,慢指针走一步,快指针不能走大于2的步数,会造成无法遇见。 找到相遇位置以后,有两种解决办法,...
  • 一、如何获得链表的中间节点 普通方法: 1、先通过遍历得到链表的长度 2、然后再通过长度遍历得到链表的中间节点 3、当然有一些链表通过一个特殊的头节点记录链表的长度的情况,可能要简单一些。 总公需要...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null //创建一个 public void crateLoop1() { ListNode cur=this.head; while(cur.next != null) { cur=cur.next; } cur.next=this....
  • 判断链表入环节点

    2019-04-21 11:02:03
    判断链表环节点 ...当我们一个链表时我们有两种方法判断链表环节点 如图: 第一种方法(前提当链表时) 1.我们把slow=fast的节点返回 显然-4的节点返回 2.然后我们让fast变为一次走一步同时让...
  • 同时从头节点处出发,如果A指针与B指针重合了,那么我们可以说这个链表中包含,如果B指针最后为null,那么该链表不包含。既然链表包含,那怎么求这个的入口节点? 其实,这个问题可以转化为数学问题来解释...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null。 package Test; public class D2 { private ListNode getIntersect(ListNode head){ ListNode tortoise = head; ListNode hare = ...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null 示例: 输入:head = [3,2,0,-4], pos = 1 输出:tail connects to node index 1 解释:链表中有一个,其尾部连接到第二个节点。 二...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null 思路 快慢指针法,快指针每次走两步,慢指针每次走一步。 先判断是否有,没返回null,有则令慢指针从头 开始,快指针每次也走一步,当...
  • 如果相同,则可以判断出链表,如果不同,则继续下一次循环 package com.interview; /** * @Date 2020/5/23 10:53 * @Author by hp * @Description 环形链表 */ public class NodeCycleDe
  • 问题: 给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 NULL 思路:针对这个题,需要分情况讨论。有存在和无存在两种情况。 如何确定链表是否带?可以利用快慢指针的思路(定义一个快...
  • //给定一个链表,返回链表开始入环的第一个节点。 如果链表,则返回 null //为了表示给定链表中的,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有...
  • 求有环链表上的第一个节点,即的起始点。 这个问题其实是分为两部分的 (1)判断一个链表是不是有循环链存在。 我们可以设置两个指针fast,flow 。 fast是每次向下移动两个节点,low是每次向下移动一个节点。如果...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,594
精华内容 18,237
关键字:

链表的入环节点