日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：翟天保Steven ? 更新時間： 2022-02-09 編程語言

題目描述

輸入一個長度為 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;
    }
};

原文鏈接：https://blog.csdn.net/zhaitianbao/article/details/121929835

欄目分類
最近更新