当前位置 博文首页 > Scissors_初夏的博客:初夏小谈:找链表倒数第K个结点
因为单链表不同于数组,数组可以用下标来访问数组中任意一个数据,而单链表却只能依靠于结点的地址来一个一个查找。
对此就可以让定义一个快指针和一个慢指针。慢指针也指向第一个结点。一个快指针先走k-1步,因为快指针初识指向第一个结点,然后让两个指针一起走。另外要注意K的范围,及边界的判定问题。
代码如下:
LinkListNode* FindKLinkList(LinkList* first, int k)
{
assert(first);
int num = 0;
if ((k < 1) || (first->head == NULL))
{
return NULL;
}
LinkListNode* Fastptr = first->head;//快指针先走K-1步
LinkListNode* Slowptr = first->head;//慢指针指向头指针
while (Fastptr != NULL)
{
if (num + 1 == k)
{
while (Fastptr->next != NULL)
{
Fastptr = Fastptr->next;//快慢指针一起走
Slowptr = Slowptr->next;
}
return Slowptr;
}
num++;
Fastptr = Fastptr->next;
}
return NULL;
}
cs此外,还有一种方法就是先遍历一边链表,并且记录结点个数对应的地址。然后找到对应的地址。这种方法虽然和二指针法的时间复杂度都是O(n),但这种方法的空间复杂度却为O(n)。(需要开辟数组来记录地址)。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍&源码