C++解決輸出鏈表中倒數k個結點的問題
題目描述
輸入一個長度為 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!