在循环单向链表中找到循环起始点的解决方案

10 浏览
0 Comments

在循环单向链表中找到循环起始点的解决方案

对于这个问题，我找到的常见解决方法是使用两个指针以不同的间隔遍历链表（例如，让p1每次遍历一个节点，p2每次遍历两个节点），直到p1和p2相等为止。示例：在单链表中找到循环

但是为什么我们不能只使用一个Set来查看是否有重复节点（前提是我们的节点没有重写默认的equals和hashCode方法）？

0

1 答案

0 Comments

循环链表是一种特殊的链表，其最后一个节点指向链表中的某个节点，形成一个循环。在循环链表中，有时候需要找到循环的起点。下面给出了解决这个问题的算法，并提供了一个C#语言的示例。

算法的实现如下：

1. 定义两个指针slow和fast，初始时都指向链表的第一个节点。

2. 进入一个无限循环。在循环中，判断slow和fast是否为空，如果为空，则说明链表不是循环链表，返回false。

3. 判断slow和fast是否相等，如果相等，则说明链表是循环链表，返回true。

4. 将fast指针向前移动两个位置，如果fast的下一个节点不为空，则再向前移动一个位置。

5. 将slow指针向前移动一个位置。

6. 继续下一轮循环。

下面是一个C#语言的示例，演示了如何使用上述算法来找到循环链表的起点。

public class Node
{
    public Node Next { get; set; }
    public T Value { get; set; }
}
class LinkedList
{
    public Node First { get; set; }
    public Node Last { get; set; }
    public void Add(T value)
    {
        Add(new Node { Value = value });
    }
    public void Add(Node node)
    {
        if (First == null)
        {
            First = node;
            Last = node;
        }
        else
        {
            Last.Next = node;
            Last = node;
        }
    }
}
static int IndexOfCiruclarity(LinkedList llist)
{
    var slow = llist.First;
    var fast = slow.Next;
    int index = -1;
    while (true)
    {
        index++;
        if (slow == null || fast == null)
            return -1;
        if (fast == slow)
            return index;
        fast = fast.Next;
        if (fast != null) fast = fast.Next;
        else
            return -1;
        slow = slow.Next;
    }
}
void TestCircularity()
{
    LinkedList r = new LinkedList();
    for (int i = 0; i < 10; i++)
        r.Add(i);
    r.Add(r.First);
    var ci = IndexOfCiruclarity(r);
    //ci = 9
}

以上就是解决循环链表中找到循环起点的问题的算法和示例。通过使用上述算法，我们可以在循环链表中找到循环的起点。

0