输出链表倒数第二个结点

忘了BAT谁家有一道面试题是输入一个单链表，输出链表倒数第二个结点，那拓展一下就是输出倒数第k个结点

常规方法是，先求链表长度N，然后从头结点开始，不断往前，直到N-k+1即可

废话不说，上代码：

struct node
{
int data;
struct node* next;
};

struct node *getK1(struct node *list, int k)
{
int n = length(list);
if(k>n)
return NULL;
struct node *current = list;   //头指针current
int i ;
for(i=0; i<n-k; i++)         
current = current->next;
return current;
};

int length(struct node *head)
{
struct node *current = head;
int count = 0;
while(current ! =NULL)
{
cout++;
current = current->next;
}
return count;

}

后又发现一个猥琐的方法，不需求链表长度即可。设置两个指针p，q，起始均指向头结点，p先向前走k步，达到第k+1个结点,此时p与q间隔了k个结点。p，q同时往前走，当p指向表尾NULL时停止，此时q向前走了N-k步，其所达到的结点就是倒数第k个结点了。

struct node *getK(struct node *head, int k)  
{  
    struct node *p, *q;  
    p = q = head;       
    for (; k>0 && p!=NULL; k--)  
        p = p->next;   
    if (k > 0) return NULL;    
    while (p != NULL) {   
        p = p->next;  
        q = q->next;  
    }  
    return p1;  
}