C++解決輸出鏈表中倒數(shù)k個結(jié)點的問題
題目描述
輸入一個長度為 n 的鏈表，設鏈表中的元素的值為 ai ，返回該鏈表中倒數(shù)第k個節(jié)點。
如果該鏈表長度小于k，請返回一個長度為 0 的鏈表。
數(shù)據(jù)范圍：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時，對應的鏈表結(jié)構(gòu)如下圖所示：
其中藍色部分為該鏈表的最后2個結(jié)點，所以返回倒數(shù)第2個結(jié)點（也即結(jié)點值為4的結(jié)點）即可，系統(tǒng)會打印后面所有的節(jié)點來比較。
示例
輸入：
{1,2,3,4,5},2
返回值：
{4,5}
說明：
返回倒數(shù)第2個節(jié)點4，系統(tǒng)會打印后面所有的節(jié)點來比較。
解題思路
本題考察數(shù)據(jù)結(jié)構(gòu)鏈表的使用。本題常用兩種思路，一種是比較基礎的，就是用容器把鏈表指針依次存儲，輸出倒數(shù)第k個即可，這樣空間復雜度為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;
}
};
到此這篇關于C++解決輸出鏈表中倒數(shù)k個結(jié)點的問題的文章就介紹到這了,更多相關C++輸出鏈表中倒數(shù)k個結(jié)點內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了插入排序的順序表實現(xiàn)代碼，有需要的朋友可以參考一下2014-01-01
VC下通過系統(tǒng)快照實現(xiàn)進程管理的方法
這篇文章主要介紹了VC下通過系統(tǒng)快照實現(xiàn)進程管理的方法,較為詳細的講述了VC下通過系統(tǒng)快照實現(xiàn)進程管理的原理與具體實現(xiàn)方法,非常具有實用價值,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C++中的數(shù)組引用和指針引用詳細的相關資料,需要的朋友可以參考下面文章內(nèi)容2021-09-09
今天小編就為大家分享一篇關于C語言用fstat函數(shù)獲取文件的大小方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
Visual Studio 2019安裝、測試創(chuàng)建c語言項目(圖文教程)
這篇文章主要介紹了Visual Studio 2019安裝、測試創(chuàng)建c語言項目，Visual Studio 2019是完全免費的，而且安裝比較簡單，現(xiàn)在把安裝步驟分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-03-03
本文主要介紹了VSCode C/C++多文件編譯配置小結(jié),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-08-08
數(shù)據(jù)結(jié)構(gòu) 中數(shù)制轉(zhuǎn)換(棧的應用)
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu) 中數(shù)制轉(zhuǎn)換(棧的應用)的相關資料,需要的朋友可以參考下2017-06-06
C++數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)鄰接表與鄰接矩陣的相互轉(zhuǎn)換
這篇文章主要為大家學習介紹了C++如何實現(xiàn)鄰接表與鄰接矩陣的相互轉(zhuǎn)換，文中的示例代碼簡潔易懂，感興趣的小伙伴可以跟隨小編一起學習一下2023-07-07
死鎖是指多個線程因競爭資源而造成的僵局（互相等待）；有些公共數(shù)據(jù)修改的機會很少，但其讀的機會很多。并且在讀的過程中會伴隨著查找，給這種代碼加鎖會降低我們的程序效率。讀寫鎖可以解決這個問題；2022-05-05
在測試程序接口運行時間的時候，常用time,gettimeofday等函數(shù)，但是這些函數(shù)在程序執(zhí)行的時候是耗費時間的2013-07-07