快捷導(dǎo)航

C++解決輸出鏈表中倒數(shù)k個(gè)結(jié)點(diǎn)的問題

更新時(shí)間：2021年12月15日 08:46:03 作者：翟天保Steven

這篇文章主要給大家介紹了關(guān)于如何利用C++解決輸出鏈表中倒數(shù)k個(gè)結(jié)點(diǎn)的問題,文中通過實(shí)例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

題目描述

輸入一個(gè)長度為 n 的鏈表，設(shè)鏈表中的元素的值為 ai ，返回該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。

如果該鏈表長度小于k，請(qǐng)返回一個(gè)長度為 0 的鏈表。

數(shù)據(jù)范圍：0<=n<=10^5，0<=ai<=10^9，0<=k<=10^9

要求：空間復(fù)雜度O(n)，時(shí)間復(fù)雜度O(n)

進(jìn)階：空間復(fù)雜度O(1)，時(shí)間復(fù)雜度O(n)

例如輸入{1,2,3,4,5},2時(shí)，對(duì)應(yīng)的鏈表結(jié)構(gòu)如下圖所示：

其中藍(lán)色部分為該鏈表的最后2個(gè)結(jié)點(diǎn)，所以返回倒數(shù)第2個(gè)結(jié)點(diǎn)（也即結(jié)點(diǎn)值為4的結(jié)點(diǎn)）即可，系統(tǒng)會(huì)打印后面所有的節(jié)點(diǎn)來比較。

示例

輸入：

{1,2,3,4,5},2

返回值：

{4,5}

說明：

返回倒數(shù)第2個(gè)節(jié)點(diǎn)4，系統(tǒng)會(huì)打印后面所有的節(jié)點(diǎn)來比較。

解題思路

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

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

測試代碼

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐ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;
        }
        // 當(dāng)快指針走完時(shí)，慢指針的位置就是倒數(shù)第k個(gè)結(jié)點(diǎn)
        while(fast != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

補(bǔ)充

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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐ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個(gè)結(jié)點(diǎn)的問題的文章就介紹到這了,更多相關(guān)C++輸出鏈表中倒數(shù)k個(gè)結(jié)點(diǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: