# Golang中怎么利用LeetCode实现一个环形链表 ## 前言 在算法和数据结构的学习中,环形链表(Circular Linked List)是一个经典问题。LeetCode平台提供了多个相关题目(如141题和142题),帮助我们深入理解链表的环形检测和入口点查找。本文将详细讲解如何在Golang中利用LeetCode题目实现环形链表的相关操作。 --- ## 一、环形链表基础概念 ### 1.1 什么是环形链表 环形链表是指链表的最后一个节点不再指向`nil`,而是指向链表中的某个先前节点,形成闭环。这种结构在内存管理和特定算法中有重要应用。 ### 1.2 环形链表的应用场景 - 内存池管理 - 轮询调度算法 - 约瑟夫问题(Josephus Problem) --- ## 二、LeetCode环形链表题目解析 ### 2.1 LeetCode 141. 环形链表(简单) **题目要求**:给定一个链表,判断链表中是否有环。 #### 解题思路:快慢指针法 ```go /** * 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, fast := head, head.Next for fast != nil && fast.Next != nil { if slow == fast { return true } slow = slow.Next fast = fast.Next.Next } return false }
进阶问题:如果有环,返回环的起始节点。
func detectCycle(head *ListNode) *ListNode { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next if slow == fast { // 找到相遇点后,重置一个指针到头部 ptr := head for ptr != slow { ptr = ptr.Next slow = slow.Next } return ptr } } return nil }
设环外长度a,环内相遇点距离入口b,剩余环长c: - 快指针路程:a + n(b+c) + b - 慢指针路程:a + b - 根据2(a+b) = a+n(b+c)+b 推导出 a = c + (n-1)(b+c)
type ListNode struct { Val int Next *ListNode }
// 创建带环链表 // pos 表示尾节点连接的节点索引(0-based) func createCircularList(vals []int, pos int) *ListNode { if len(vals) == 0 { return nil } nodes := make([]*ListNode, len(vals)) for i, val := range vals { nodes[i] = &ListNode{Val: val} if i > 0 { nodes[i-1].Next = nodes[i] } } if pos >= 0 && pos < len(nodes) { nodes[len(nodes)-1].Next = nodes[pos] } return nodes[0] }
func TestHasCycle(t *testing.T) { // 测试用例1:无环链表 list1 := createCircularList([]int{1,2,3}, -1) assert.False(t, hasCycle(list1)) // 测试用例2:有环链表 list2 := createCircularList([]int{3,2,0,-4}, 1) assert.True(t, hasCycle(list2)) }
func josephus(n, m int) int { // 创建环形链表 head := &ListNode{Val: 1} current := head for i := 2; i <= n; i++ { current.Next = &ListNode{Val: i} current = current.Next } current.Next = head // 形成环 // 开始淘汰 for current.Next != current { // 移动m-1步 for i := 1; i < m; i++ { current = current.Next } // 淘汰下一个节点 current.Next = current.Next.Next } return current.Val }
通过LeetCode的环形链表题目,我们掌握了: 1. 快慢指针检测环的高效算法 2. 环入口点的数学推导方法 3. Golang实现环形链表的完整方案
建议读者在理解基础上尝试以下扩展: - 实现环形链表的插入/删除操作 - 解决LeetCode 287(寻找重复数)的环形链表解法 - 探索Redis的LRU缓存淘汰算法与环形链表的关系
学习提示:可以修改
createCircularList
函数生成不同测试用例,使用go test -v
验证算法正确性。 “`
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。