c-单链表最后一个节点指向列表中的任意节点

Question

我有一个链表。假设单链表的最后一个节点不是null，并指向列表中的某个任意节点，而不是null（这意味着它不是''）。因此，链表循环，但不指向第一个节点。我想找到链表的最后一个节点。你能给我建议解决这个问题的算法吗？

Answer 1

我认为这正是您所需要的。

将head初始化为两个指针。

int *temp1 = head, *temp2 = head;

一个指针比另一个指针的步长增加两倍。如果链表有循环，则两个指针将在循环中的某个点相遇。让我们使用temp2来存储此会议点节点。

while (temp1 != temp2)
{
  temp1 = temp1->next;
  temp1 = temp1->next;
  temp2 = temp2->next;
}

迭代一个指针（temp1）来循环并计算其长度。

temp1 = temp1->next; // At this point temp1 is the node of the meeting point
loop_length = 0;
while (temp1 != temp2)
{
  temp1 = temp1->next;
  loop_length++;
}

初始化指向head的指针temp1并前进loop_length步数。

temp1 = head;
while (i < loop_length)
{
  temp1 = temp1->next;
  i++;
}

将另一个指针temp3初始化为head，然后同时迭代temp1和temp3，直到它们相遇。在循环终止之后，两者将在循环的起点相遇。

temp3 = head;
while (temp1 != temp3)
{
  temp1 = temp1->next;
  temp3 = temp3->next;
}

现在，您可以从temp3开始获取另一个指针temp4，并遍历列表，直到temp4->next和temp3相遇。

temp4 = temp3;
while (temp4->next != temp3)
{
  temp4 = temp4->next;
}

现在temp4将位于列表的末尾。

Answer 2

据我所知，您有这样的东西，其中整数只是用于命名节点的标签：

1 -> 2 -> 3 -> 4 -> 2

我想您在问如何检测节点4指向列表中较早发生的某个事件。我认为根据你的定义，4将是列表的末尾。请验证！

在这种情况下，最简单的方法是从列表的开头开始，每次都将节点标记为已访问（如果可以为此添加数据），或者保留一组已访问节点的结构。在每个步骤中，您都可以看到下一个节点是否在访问集中。如果是，则表示已找到最后一个节点，如果不是，则将其放入集合中并继续。

因此，对于这些数据，我们得到

current  next  visited       Comment
-------  ----  -------       -------
    1      2    {1}
    2      3    {1, 2}
    3      4    {1, 2, 3}
    4      2                 Stop, 2 is in visited, so 4 is the "last" node.

Answer 3

如果我正确理解你的问题。您有一个链表，其中最后一个指针指向以前的条目，如

This     Next      Etc.
   1        2      xxxx
   2        3      xxxxx
   3        4
   4        5
   6        3

因此，你需要保留一个你已经访问过的条目表。当您在表中找到一个"下一个"值时，当前条目就是列表中真正的最后一个条目。

即

do forever
   visited[This] = "Y";
   move to Next
   if visited[Next] == "Y" 
      exit loop
   next;