闲逛的时候，看到一据说是腾讯的笔试题：
找出单链表的倒数第n个节点，自己写了一下：
- typedef struct node
- {
- int data;
- struct node *next;
- } link_node;
- //第一种方法
- // 找出倒数第n个节点，返回其指针
- link_node *find_n (link_node *head, int n)
- {
- link_node *p = head;
- int num_node = 0;
- if (p == NULL) //链表为空
- {
- printf ("the link list is empty./n");
- return NULL;
- }
- while (p->next != NULL) //统计节点个数 复杂度:O(list_length)
- {
- num_node++;
- p = p->next;
- }
- if (num_node < n)
- {
- printf ("the length of the link list is %d/n", num_node);
- return NULL;
- }
- //总共有num_node个，则倒数第n个即正数第num_node-n+1个
- p = head;
- int i = 1;
- while (i < num_node - n + 1) //时间复杂度:O(list_length-n)
- {
- p = p->next;
- i++;
- }
- return p;
- }
- // 第二种方法
- /** 设置两个指针p1,p2，让p1与p2间隔n-1个节点，即让p2指向
- 正数第n个节点，然后顺次后移,
- 当p2到达末尾时，p1指向倒数第n个节点
- */
- link_node *find_n (link_node *head, int n)
- {
- link_node *p1 = head, *p2 = head;
- int i = 1;
- while ((i < n) && (p2 != NULL))
- {
- p2 = p2->next;
- i++;
- }
- if (i != n) //说明链表节点个数不足n
- {
- printf ("the node number is less than %d/n", n);
- return NULL;
- }
- while (p2->next != NULL)
- {
- p1 = p1->next;
- p2 = p2->next;
- }
- return p1;
- }
可能有的同学认为第一种方法不值一提，但分析一下时间复杂度，会发现两种方法的时间复杂度都是O(list_length) + O(list_length-n)。
如哪位兄台有更好的办法，不妨指点一下。