题目：
输入一个链表，输出该链表中倒数第k个结点。
思路1：
使用指针遍历链表，得到链表的长度len；将指针指向链表头部，向后移动len-k+1个长度，得到倒数第k个节点。
代码1：
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 ListNode *newphead =
pListHead;
13 int total =
0;
14 while(newphead !=
NULL){
15 total++
;
16 newphead = newphead->
next;
17 }
18 newphead =
pListHead;
19 int flag = total-k+
1;
20 total =
0;
21 ListNode *
result;
22 while(newphead !=
NULL){
23 total++
;
24 if(total ==
flag){
25 result =
newphead;
26 break;
27 }
28 newphead = newphead->
next;
29 }
30 return result;
31 }
32 };
View Code
思路2：
使用两个指针，第一个指针向前移动k-1个节点，到达第k个节点；第二个指针和第一个指针同时开始移动，当第一个指针到达链表末尾时，第二个指针位于倒数第k个节点上。
代码2：
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(pListHead ==
NULL )
13 return pListHead;
14 ListNode *p1 =
pListHead;
15 ListNode *p2 =
pListHead;
16 int step =
1;
17 while(step <=
k){
18 if(p1->next !=
NULL)
19 p1 = p1->
next;
20 else{
21 if(step ==
k)
22 return p2;
23 else
24 return NULL;
25 }
26 step +=
1;
27 }
28 while(p1 !=
NULL){
29 p1 = p1->
next;
30 p2 = p2->
next;
31 }
32 return p2;
33 }
34 };
View Code
转载于:https://www.cnblogs.com/sindy/p/7387708.html
相关资源：数据结构—成绩单生成器
