您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 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进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。