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

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a

题意

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

题解

单向链表没有指向上个节点的指针，所以无法倒数。
可以正着扫一遍，计算总长度，然后就可以计算出是正数第几个。然后再扫描一遍。
也可以不扫两遍，用两个指针，p和q,p先移动，移动到第k个节点是，q开始移动，p移动到末尾时，q正好为倒数第k个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==NULL||k==0) return NULL;
        ListNode * p=pListHead,*q=pListHead;
        int pc=1;
        while(p){
            if(pc>k) q=q->next;
            p=p->next;
            pc++;
        }
        if(pc<=k) return NULL;
        return q;
    }
};