c# - 我如何找到它是否是重复播放列表？

Question

我需要查看播放列表是否重复。从我下面的代码中请帮助提出解决方案。如果任何歌曲包含对播放列表中先前歌曲的引用，则播放列表被视为重复播放列表。否则，播放列表将以最后一首指向 null 的歌曲结束。

using System;

public class Song
{
    private string name;
    public Song NextSong { get; set; }

    public Song(string name)
    {
        this.name = name;
    }

    public bool IsRepeatingPlaylist()
    {
        if(this.name == NextSong.name)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void Main(string[] args)
    {
        Song first = new Song("Hello");
        Song second = new Song("Eye of the tiger");

        first.NextSong = second;
        second.NextSong = first;

        Console.WriteLine(first.IsRepeatingPlaylist());
    }
}

标签： c#class

Answer 1

这似乎等同于检查链表中的循环，因此我们可以简单地使用Floyd 的“龟兔赛跑”循环检测算法：

public bool IsRepeatingPlaylist()
{
    var tortoise = this;
    var hare     = NextSong;

    while (tortoise is not null && hare is not null)
    {
        if (ReferenceEquals(tortoise, hare))
            return true;

        tortoise = tortoise.NextSong;
        hare     = hare.NextSong?.NextSong; // Twice as fast.
    }

    return false;
}

这是一些测试播放列表的代码，其中播放列表的末尾循环回到播放列表大约一半的歌曲：

static void Main()
{
    Song start = new Song("1");
    Song curr  = start;

    Song halfway = null;

    for (int i = 2; i < 100; ++i)
    {
        curr.NextSong = new Song(i.ToString());
        curr = curr.NextSong;

        if (i == 50)
            halfway = curr;
    }

    curr.NextSong = halfway;
    Console.WriteLine(start.IsRepeatingPlaylist());
}