141. Linked List Cycle

Leetcode 問題: 141. Linked List Cycle
Categories:
Tags:

題目

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

判斷鏈結是否存在循環迴圈，若快節點能追上慢節點，則表示一定有存在循環迴圈

答案

Floyd’s Cycle Detection

Golang

// 判斷鏈結是否存在循環迴圈，若快節點能追上慢節點，則表示一定有存在循環迴圈
func hasCycle(NumberListNode *ListNode) bool {
	// 設定快慢節點
	fastListNode := NumberListNode
	slowListNode := NumberListNode
	for fastListNode != nil && fastListNode.Next != nil {
		// 當快捷點有資料，且有下一個節點的資料
		// 快節點往後移動 2 個節點
		fastListNode = fastListNode.Next.Next
		// 慢節點往後移動 1 個節點
		slowListNode = slowListNode.Next
		if fastListNode == slowListNode {
			// 快節點與慢節點相同，此鏈結存在循環迴圈
			return true
		}
	}
	return false
}

完整程式碼

package main

import (
	"fmt"
)

type Question struct {
	// 參數
	Parameter
	// 答案
	Answer
}

// 參數
type Parameter struct {
	NumberList []int
}

// 答案
type Answer struct {
	result bool
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func main() {

	QuestionList := []Question{
		{
			Parameter{[]int{3, 2, 0, -4}},
			Answer{false},
		},

		{
			Parameter{[]int{1, 2}},
			Answer{false},
		},

		{
			Parameter{[]int{1}},
			Answer{false},
		},
	}

	fmt.Printf("------------------------Leetcode Problem 141. Linked List Cycle------------------------\n")
	for _, question := range QuestionList {
		param := question.Parameter
		expectAnswer := question.Answer
		exactAnswer := hasCycle(Ints2List(param.NumberList))
		fmt.Printf("【input】:%v       【output】:%v     【expect】:%v\n", param, exactAnswer, expectAnswer.result)
	}
}

// 判斷鏈結是否存在循環迴圈，若快節點能追上慢節點，則表示一定有存在循環迴圈
func hasCycle(NumberListNode *ListNode) bool {
	// 設定快慢節點
	fastListNode := NumberListNode
	slowListNode := NumberListNode
	for fastListNode != nil && fastListNode.Next != nil {
		// 當快捷點有資料，且有下一個節點的資料
		// 快節點往後移動 2 個節點
		fastListNode = fastListNode.Next.Next
		// 慢節點往後移動 1 個節點
		slowListNode = slowListNode.Next
		if fastListNode == slowListNode {
			// 快節點與慢節點相同，此鏈結存在循環迴圈
			return true
		}
	}
	return false
}

// Ints2List convert []int to List
func Ints2List(NumberList []int) *ListNode {
	if len(NumberList) == 0 {
		return nil
	}

	HeadListNode := &ListNode{}
	NextListNode := HeadListNode
	for _, v := range NumberList {
		NextListNode.Next = &ListNode{Val: v}
		NextListNode = NextListNode.Next
	}
	return HeadListNode.Next
}

參考資料