本題考察數(shù)據(jù)結(jié)構(gòu)鏈表的使用。本題常用兩種思路，一種是比較基礎(chǔ)的，就是用容器把鏈表指針依次存儲，輸出倒數(shù)第k個即可，這樣空間復(fù)雜度為O(n)；另一種進階解法，快慢指針法，讓快指針先走k步，當它走到頭時，此時慢指針的位置就是倒數(shù)第k個結(jié)點。

測試代碼為快慢指針法，容器法比較簡單就不寫了。

測試代碼

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param pHead ListNode類 
     * @param k int整型 
     * @return ListNode類
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // 空鏈表直接返回
        if(pHead == NULL)
            return pHead;
        // 快慢指針
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        // 讓快指針先走k步
        while(k--)
        {
            if(fast == NULL)
                return NULL;
            fast = fast->next;
        }
        // 當快指針走完時，慢指針的位置就是倒數(shù)第k個結(jié)點
        while(fast != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

補充

第二種實現(xiàn)方法：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param pHead ListNode類 
     * @param k int整型 
     * @return ListNode類
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        ListNode* p=pHead;
        ListNode* q=pHead;
        if(pHead==NULL)return NULL;
        while(k--)
        {
            if(q==NULL)return NULL;
            q=q->next;
            
            //k--;
        }
        //if(q==NULL)return pHead;
        while(q)
        {
            p=p->next;
            q=q->next;
        }
        return p;
    }
};

到此這篇關(guān)于C++解決輸出鏈表中倒數(shù)k個結(jié)點的問題的文章就介紹到這了,更多相關(guān)C++輸出鏈表中倒數(shù)k個結(jié)點內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: