Go中怎么遍历环形链表

小亿

2024-04-03 09:59:05

栏目: 编程语言

在Go中遍历环形链表可以通过两种方法实现：

快慢指针法：使用两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。如果链表中有环，那么这两个指针最终会相遇。具体实现代码如下：

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 fast != nil && fast.Next != nil {
        if slow == fast {
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return false
}

标记法：遍历链表时，给每个节点一个标记，如果发现已经访问过的节点，则说明链表有环。具体实现代码如下：

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    cur := head
    for cur != nil {
        if cur.Val == -1 {
            return true
        }
        cur.Val = -1
        cur = cur.Next
    }
    return false
}

Go中怎么遍历环形链表

最新问答

相关标签