2

我有单链表。假设单链表的最后一个节点不为空,并指向列表中的某个任意节点而不是 NULL(这意味着它不是'\0')。因此链表循环但它不指向第一个节点。我想找到链表的最后一个节点。你能建议我解决这个问题的任何算法吗?

4

3 回答 3

5

我认为这是你需要的。

初始化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++;
}

初始化一个指针temp1head推进步loop_length数。

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

初始化另一个指针temp3head然后同时迭代两者temp1temp3直到它们相遇。循环终止后,两者将在循环的起点相遇。

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将有列表的末尾。

于 2013-07-26T06:49:38.287 回答
1

据我了解,您有这样的事情,其中​​整数只是为了命名节点的标签:

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.
于 2013-07-26T06:25:39.030 回答
0

如果我正确理解你的问题。您有一个链表,其中最后一个指针指向上一个条目,如下所示

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

所以你需要保留一个你已经访问过的条目表。当您找到表中已经存在的“下一个”值时,当前条目就是列表中真正的最后一个条目。

IE

do forever
   visited[This] = "Y";
   move to Next
   if visited[Next] == "Y" 
      exit loop
   next;
于 2013-07-26T06:30:55.220 回答