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

Question

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

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++;
}

初始化一个指针temp1到head与预先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;
}

现在，您可以采取另一种指针temp4从开始temp3并遍历列表，直到temp4->next和temp3满足。

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

现在temp4将在列表的末尾。