在鏈表中找出倒數(shù)第K個(gè)節(jié)點(diǎn)

（1）遍歷兩遍，第一次計(jì)算出鏈表長(zhǎng)度n，第二次找到（n-k）個(gè)節(jié)點(diǎn)，也就是倒數(shù)第K個(gè)節(jié)點(diǎn)。

（2）遍歷一遍，定義兩個(gè)指針，一個(gè)指針fast,一個(gè)指針slow,都指向頭結(jié)點(diǎn)，fast指針先向前走K，然后再同時(shí)遍歷，當(dāng)fast遍歷到最后一個(gè)節(jié)點(diǎn)時(shí)，slow所指向的節(jié)點(diǎn)就是倒數(shù)第K個(gè)節(jié)點(diǎn)。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
struct Listnode
{
    int _value;
    Listnode* _next;
};
void Init(Listnode*& head)
{
    Listnode* cur =head;
    if(cur==NULL)
    {
        cur=(Listnode*)malloc(sizeof(Listnode));
        cur->_next=NULL;
        cur->_value=0;
    }
    head=cur;
}
 
void push(Listnode*& head,int value)
{
    Listnode* cur =head;
 
        while(cur->_next)
        {
            cur=cur->_next;
        }
        Listnode* tmp=NULL;
        tmp=(Listnode*)malloc(sizeof(Listnode));
        tmp->_next=NULL;
        tmp->_value=value;
        cur->_next=tmp;
     
         
 
}
void pop(Listnode* head)
{
    Listnode* cur=head;
    Listnode* prev=NULL;
    while(cur->_next!=NULL)
    {
        prev=cur;
        cur=cur->_next;
    }
    prev->_next=NULL;
    free(cur);
    cur=NULL;
}
void print(Listnode* head)
{
    Listnode* cur=head;
    while(cur)
    {
        printf("%d\n",cur->_value);
        cur=cur->_next;
    }
}
Listnode* Find(Listnode* head,int k)
{
    assert(head);
	assert(k>0);
	Listnode* slow=head;
	Listnode* fast=head;
	while(k--)
	{
		fast=fast->_next;
	}
	while(fast)
	{
		slow=slow->_next;
		fast=fast->_next;
	}
	return slow;

}

void test()
{
    Listnode* head=NULL;
    Init(head);
    push(head,1);
    push(head,2);
    push(head,3);
    /*pop(head);*/
     print(head);
	Listnode* ret=Find(head,2);
	printf("倒數(shù)第K個(gè)數(shù)：%d\n",ret->_value);
   
 
}
int main()
{
    test();
    system("pause");
    return 0;
}

結(jié)果：