我有单链表。假设单链表的最后一个节点不为 null 并指向列表中的某个任意节点而不是 NULL(这意味着它不是 '\0'
)。因此链表循环但它不指向第一个节点。我想找到链表的最后一个节点。你能建议我解决这个问题的任何算法吗?
最佳答案
我认为这就是您所需要的。
将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
将到达列表的末尾。
关于c - 单链表最后一个节点指向列表中的任意节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17874220/