C++解決輸出鏈表中倒數k個結點的問題

Posted on by

題目描述

輸入一個長度為 n 的鏈表，設鏈表中的元素的值為 ai ，返回該鏈表中倒數第k個節點。

如果該鏈表長度小於k，請返回一個長度為 0 的鏈表。

數據范圍：0<=n<=10^5，0<=ai<=10^9，0<=k<=10^9

要求：空間復雜度O(n)，時間復雜度O(n)

進階：空間復雜度O(1)，時間復雜度O(n)

例如輸入{1,2,3,4,5},2時，對應的鏈表結構如下圖所示：

其中藍色部分為該鏈表的最後2個結點，所以返回倒數第2個結點（也即結點值為4的結點）即可，系統會打印後面所有的節點來比較。

示例

輸入：

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

返回值：

{4,5}

說明：

返回倒數第2個節點4，系統會打印後面所有的節點來比較。

解題思路

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

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

測試代碼

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
     *
     * 
     * @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;
        }
        // 當快指針走完時，慢指針的位置就是倒數第k個結點
        while(fast != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

補充

第二種實現方法：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
     *
     * 
     * @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;
    }
};

到此這篇關於C++解決輸出鏈表中倒數k個結點的問題的文章就介紹到這瞭,更多相關C++輸出鏈表中倒數k個結點內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：