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

发表于 | 分类于

题目描述

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

思路分析

运用双指针法，两个指针均指向头结点。其中一个指针p1先走k个结点，然后再让两个指针同时走，当p1走到末尾时，此时p2指针所指结点即为倒数第k个结点。但特别要注意的是，要考虑边界条件！！每道题，都要优先考虑边界条件！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
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) return NULL;
        ListNode *p1 = pListHead, *p2 = pListHead; // p1指针先走k个结点
        while(p1 && k){
            p1 = p1->next;
            k--;
        }
        if(!p1 && k>0) return NULL;
        while(p1){
            p2 = p2->next;
            p1 = p1->next;
        }
        return p2;
    }
};