剑指Offer 链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

思路：

法1：设置2个指针p，q。p先移动k次，然后pq同时后移，p到链表尾尾的时候，q指向倒数第k个节点。

　　　　注意：//需要考虑k=0，以及List为空的情况

法2：利用栈，先全部压栈，pop k次，得到倒数第k个节点

AC代码：

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
12         if(k==0||pListHead==NULL)   //需要考虑k=0，以及List为空的情况
13             return NULL;       
14         
15         ListNode *p,*q;
16         p=pListHead;
17         q=pListHead;
18         
19         for(int i=1;i<k;i++)  //注意边界值，从1开始
20         {
21             if(p->next!=NULL)
22                 p=p->next;
23             else
24                 return NULL;
25         }
26         
27         while(p->next!=NULL)
28         {
29             p=p->next;
30             q=q->next;
31         }
32         
33         return q;
34     
35     }
36 };