《劍指offer》連結清單中倒數第k個結點

一、題目描述

輸入一個連結清單，輸出該連結清單中倒數第k個結點。

二、輸入描述

一個連結清單

三、輸出描述

連結清單的倒數第k個結點

四、牛客網提供的架構

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {

    }
};
           

五、解題思路

建兩個結點指針，一個指針為起始節點，另外一個位距離起始節點長度為k的末尾節點。從原連結清單的頭開始不斷向後尋找，當末尾節點找到最後時，起始節點所隻想的是倒數第k個節點。

尋找過程如下圖：

六、代碼

/*
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(k <= ) return NULL;

        ListNode *goalNode, *kNode;
        goalNode = pListHead;
        kNode = goalNode;
        for(int i = ; i < k; i++)
        {
            if(kNode) kNode = kNode->next;

            if(!kNode) return NULL;

        }

        while(kNode && kNode->next)
        {
            kNode = kNode->next;
            goalNode = goalNode->next;
        }

        return goalNode;

    }
};
           

轉載于:https://www.cnblogs.com/chenximcm/p/6285122.html