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
}

参考资料