查找链表中倒数第k个结点

时间：2009-07-21 来源：ubuntuer

输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
刚开始想的是先遍历一遍求出链表的大小n,然后n-k，然后在从头走n-k个节点.想想应该不会是这样不讲究效率的.

良久发现其实有点像判断链表是不是有环,设置两个指针都指向链表的头,第一个先遍历K个节点，然后指针一指针二同时next,直到指针一指向NULL,此时指针二的位置就是所求的位置了....也有点像判断两个链表是不是相交,那个Y型了^_^.具体是

k-1还是n-k-1这些细节程序里面在考虑了。下面这个程序还有一个可取之处就是不重复的随机取数,记得以前百度好像就有这么个东东^_^.没有free习惯不好...大家别学我,我这个比较懒

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

typedef struct list
{
  int num;
  struct list* next;
}LIST;

void init_list(LIST** L)
{
  *L = (LIST*)malloc(sizeof(LIST));
  (*L)->next = NULL;
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int getrand(int A[], int start, int end)
{
   int nums = end - start + 1;
   int location = rand()%nums + start;
   swap(A+start,A+location);
   return A[start];
}

void add_list(LIST* L, int num)
{
  LIST* p = L->next;
  LIST* q = L;

  while(p!=NULL)
   {
     q = p;
     p = p->next;
    }

  p = (LIST*)malloc(sizeof(LIST));
  p->num = num;
  p->next = NULL;
  q->next = p;
}

void print_list(LIST* L)
{
  int count = 0;
  LIST* p = L->next;
  while(p!=NULL)
  {
    if(++count%5 == 0)
     printf("%d\n",p->num);
    else
     printf("%d\t",p->num);

    p = p->next;
  }
}

LIST* count_lask_k_node(LIST* L, int k)
{
  int i = 0;
  LIST* p = L->next;
  LIST* q = L->next;

  for(;i<k;i++)
    q = q->next;

while(q!=NULL)
  {
    p = p->next;
    q = q->next;
   }

  return p;
}

int main(int argc, char *argv[])
{
  int i = 0;
  int num;
  int k = 0;
  int A[N] = {1,2,3,4,5,6,7,8,9,10};
  LIST* L = NULL;
  init_list(&L);

  for(; i<N; i++)
   {
     num = getrand(A,i,N-1);
     add_list(L,num);
    }
  printf("the list is:\n");
  print_list(L);
  //k = rand()%N+1;

  k = 1;
  LIST* ret = count_lask_k_node(L,k);
  printf("the last %d node is %d\n",k,ret->num);
  system("PAUSE");
  return 0;
}