美文网首页
Golang 数据结构练习——单链表找环

Golang 数据结构练习——单链表找环

作者: redexpress | 来源:发表于2020-10-23 23:44 被阅读0次

问题:一个单向链表,怎样怎么检测是否有环,环的初始节点是什么?

package main

import (
    "fmt"
)

type ListNode struct {
    value int
    next  *ListNode
}

func NewListNode(i int) *ListNode {
    val := new(ListNode)
    val.value = i
    return val
}

func main() {
    a1 := NewListNode(1)
    a2 := NewListNode(2)
    a3 := NewListNode(3)
    a4 := NewListNode(4)
    a5 := NewListNode(5)

    // 1→2→3→4→5
    //     ↑⎽⎽⎽⌟   

    a1.next = a2
    a2.next = a3
    a3.next = a4
    a4.next = a5
    a5.next = a3
    head := DetectCycle(a1)
    fmt.Println(head.value)
}

func DetectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    for {
        if fast.next == nil || slow.next == nil {
            break
        }
        fast = fast.next.next
        slow = slow.next
        if fast == slow {
            // 找到快慢指针相遇点
            break
        }
    }
    if fast == nil || slow == nil {
        return nil
    }
    // 找到快慢指针相遇点后,快慢指针一样的速度移动,找到环的起点
    slow = head
    for {
        if fast == slow {
            break
        }
        fast = fast.next
        slow = slow.next
    }
    return slow
}


相关文章

  • Golang 数据结构练习——单链表找环

    问题:一个单向链表,怎样怎么检测是否有环,环的初始节点是什么?

  • 数据结构——Golang实现单链表

    转载请注明出处:数据结构——Golang实现单链表 1. 单链表 1.1. 定义 单向链表(单链表)是链表的一种,...

  • 数据结构与算法

    笨办法学 Python · 续 练习 13:单链表 笨办法学 Python · 续 练习 13:单链表数据结构与常...

  • 2020-08-19

    单链表找环(floyd算法) 首先是示意图,链表中有环就是这种情况 问题是,在这样一个单链表中,若有环,寻找出环的...

  • 检测链表有环

    题目:如何判断一个单链表是否有环?若有环,如何找出环的入口节点。 一、单链表是否有环 思路分析: 单链表有环,是指...

  • LeetCode-Golang之【141. 环形链表】

    给定一个链表,判断链表中是否有环。如果链表中存在环,则返回 true 。 否则,返回 false 。 Golang 题解

  • 判断单链表是否有环及寻找环的

    若单链表中存在环,则环肯定在单链表的尾部,如果通过一个指针遍历单链表,最终这个指针会在单链表尾部的环中不断循环,其...

  • 数据结构 | 其二 链表

    冰河winner - 数据结构之链表 2.1 单向链表 数据结构(一) 单链表的实现-JAVA 2.2 双端链表 ...

  • 单链表是否存在环

    面试题:如何检测一个单链表是否有环?如果有环的入口在哪里? 题目描述: 单链表有环指的是单链表中某个结点的next...

  • 算法与数据结构知识汇总(二、链表)

    1、概念 2、链表的数据结构 单向链表的数据结构如下图: 上图数据结构为单向链表,简称单链表,该数据结构由若干个节...

网友评论

      本文标题:Golang 数据结构练习——单链表找环

      本文链接:https://www.haomeiwen.com/subject/vsnbmktx.html