c++环形链表怎么实现

发布时间:2022-03-17 16:03:39 作者:iii
来源:亿速云 阅读:231

这篇文章主要介绍“c++环形链表怎么实现”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“c++环形链表怎么实现”文章能帮助大家解决问题。

算法:

该类题目的核心点在于如何判断是环形链表,核心思想是:两个人在环上跑步,跑的快的早晚会追上跑的慢的。

是快慢指针的典型使用场景。

题目1: 环形链表

代码实现:

/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func hasCycle(head *ListNode) bool {    if head == nil || head.Next == nil {        return false    }    slow := head // 慢指针一次走一步    fast := head.Next // 快指针一次走两步    for slow != fast {        if slow == nil || fast == nil {            return false        }        slow = slow.Next        fast = fast.Next        if fast != nil {            fast = fast.Next        }    }    return true}

题目2:环路检测

代码实现:

// 算法:该题目主要分两步,第一步是找到环形链表中的相交的位置。// 第二步是让慢指针指向链表首部,快指针位置不变,// 然后快慢指针每次都走一步,再次相遇就是环形链表的入口位置。/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func detectCycle(head *ListNode) *ListNode {    s, f := head,head    for f != nil && f.Next != nil {         s = s.Next        f = f.Next.Next        if f == s { // 判断是不是有环            break        }    }    if f == nil || f.Next == nil {         // 此时的快指针在环里面,理论上这两个都不应该为空;        // 只有一个节点的话,f.Next == nil        return nil    }
   s = head    for s != f {        s = s.Next        f = f.Next    }    return s}

关于“c++环形链表怎么实现”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注亿速云行业资讯频道,小编每天都会为大家更新不同的知识点。

推荐阅读:
  1. java如何实现环形链表?
  2. 【算法日常】判断环形链表

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++

上一篇:c++如何删除和为0的元素

下一篇:c++怎么计算二叉搜索树中第K小的元素

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》