数据结构：求单链表倒数第k个节点，只能遍历一次链表

categories:

• 数据结构

题目要求

求单链表倒数第k个节点，要求只能遍历一次单链表

算法

用两个指针p、q来实现，p、q都指向链表开始位置，先让p指针向后走k个位置，然后两个指针同步走，当p指针为空的时候，q指针就是倒数第k个节点

C代码

LinkList FindNodeOfK(LinkList plist, int k)
{
    if (plist == NULL || plist->next == NULL || k <= 0)
    {
        return NULL;
    }
    LinkList p = plist, q = plist;
    for (int i = 0; i < k&&p != NULL; i++)
    {
        p = p->next;
    }
    if (p == NULL)//k的值大于链表的长度
        return NULL;
    while (p != NULL)
    {
        p = p->next;
        q = q->next;
    }
    return q;
}