查找单向链表中倒数第k个节点有如下链表节点定义：Struct

[问答题]

查找单向链表中倒数第k个节点

有如下链表节点定义：

Struct Node {

int value;

Node * next;

}

nlw_strong

因为无法一开始知道链表的长度，需要通过快慢指针来做，保持其相对的距离是 K即可：

一开始快慢指针都指向头节点；

先让快指针走 k-1步；

然后慢指针从头开始走；

当快指针遍历链表结尾，慢指针的位置即是答案；

发表于 2020-09-03 16:43:14 回复(0)

牛客966787149号

typedef struct Node
{
   int value;
   Node * next;
}Node;
Node* getnode_rK(int k,Node* head)
{
    cin>>k;
    if(k==0||head->next==NULL)//链表为空或k=0
        return NULL;
    Node*Apoint=head->next;
    Node*Bpoint=head->next;
    while(k>1)//A指针先走K-1步
    {
        Apoint=Apoint->next;
        k--;
        if(Apoint==NULL)
            return NULL;
    }
    while(Apoint->next!=NULL)//A B一起走，直到A到尾结点
    {
        Apoint=Apoint->next;
        Bpoint=Bpoint->next;
    }
    return Bpoint;
}

发表于 2020-05-11 16:34:58 回复(0)