十分鐘教你學(xué)會(huì)快慢指針?lè)?/h1>
題目描述
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。為了符合大多數(shù)人的習(xí)慣，本題從1開(kāi)始計(jì)數(shù)，即鏈表的尾節(jié)點(diǎn)是倒數(shù)第1個(gè)節(jié)點(diǎn)。
例如，一個(gè)鏈表有 6 個(gè)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開(kāi)始，它們的值依次是 1、2、3、4、5、6。這個(gè)鏈表的倒數(shù)第 3 個(gè)節(jié)點(diǎn)是值為 4 的節(jié)點(diǎn)。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 k = 2.
返回鏈表 4->5.
題目分析
這是個(gè)鏈表題目，先一句句分析(其實(shí)第一句就已經(jīng)是完整的題目了)，要輸出鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。其實(shí)很容易想到遍歷，最后取倒數(shù)第k個(gè)就可以了，前提是你得知道鏈表的長(zhǎng)度。事實(shí)上，鏈表的長(zhǎng)度并不知道，需要你自己算出來(lái)。
所以我們考慮下有沒(méi)有更好的辦法，這里推薦快慢指針?lè)ā?/p>
快慢指針?lè)?/span>
如圖所示，這里遍歷鏈表時(shí)，給兩個(gè)指針，一個(gè)快，一個(gè)慢，中間相差k個(gè)節(jié)點(diǎn)，等快的那個(gè)走到最后了，慢的那個(gè)就是要的結(jié)果了。思路是不是很清晰？！
沒(méi)接觸過(guò)鏈表的可以先看這段代碼體會(huì)下鏈表節(jié)點(diǎn)的構(gòu)造：
function ListNode(val) {
this.val = val;
this.next = null;
}
下面是題解
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
var former = head,latter = head;
for(var i =0;i<k;i++){
former = former.next;
}
while(former!=null){
former = former.next;
latter = latter.next;
}
return latter
};
其中former代表的是快指針，latter是慢指針，它們的起點(diǎn)相同，都是從鏈表頭部head開(kāi)始，former先走了k個(gè)節(jié)點(diǎn)，然后慢指針latter才開(kāi)始啟動(dòng)，與快指針former同步往后走，這個(gè)差距始終都是k個(gè)節(jié)點(diǎn)。最終，當(dāng)former走完最后節(jié)點(diǎn)，變成null時(shí)，latter就是此完整鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn)了。
這里還有另一種表達(dá)方式，也可以參考，意思是一樣的。
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let fast = head;
let slow = head;
let flag = 0;
while (fast) {
if (flag >= k) {
slow = slow.next;
}
fast = fast.next;
flag ++;
}
return slow;
};
復(fù)雜度分析
時(shí)間復(fù)雜度都是O(n),n為鏈表長(zhǎng)度；空間復(fù)雜度都是O(1)，變量都是常量階的;
參考鏈接:
https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/jskuai-man-zhi-zhen-by-liberhome-dnxt/ https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
瀏覽
90
題目描述
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。為了符合大多數(shù)人的習(xí)慣，本題從1開(kāi)始計(jì)數(shù)，即鏈表的尾節(jié)點(diǎn)是倒數(shù)第1個(gè)節(jié)點(diǎn)。
例如，一個(gè)鏈表有 6 個(gè)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開(kāi)始，它們的值依次是 1、2、3、4、5、6。這個(gè)鏈表的倒數(shù)第 3 個(gè)節(jié)點(diǎn)是值為 4 的節(jié)點(diǎn)。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 k = 2.
返回鏈表 4->5.
題目分析
這是個(gè)鏈表題目，先一句句分析(其實(shí)第一句就已經(jīng)是完整的題目了)，要輸出鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。其實(shí)很容易想到遍歷，最后取倒數(shù)第k個(gè)就可以了，前提是你得知道鏈表的長(zhǎng)度。事實(shí)上，鏈表的長(zhǎng)度并不知道，需要你自己算出來(lái)。
所以我們考慮下有沒(méi)有更好的辦法，這里推薦快慢指針?lè)ā?/p>
快慢指針?lè)?/span>
如圖所示，這里遍歷鏈表時(shí)，給兩個(gè)指針，一個(gè)快，一個(gè)慢，中間相差k個(gè)節(jié)點(diǎn)，等快的那個(gè)走到最后了，慢的那個(gè)就是要的結(jié)果了。思路是不是很清晰？！
沒(méi)接觸過(guò)鏈表的可以先看這段代碼體會(huì)下鏈表節(jié)點(diǎn)的構(gòu)造：
function ListNode(val) {
this.val = val;
this.next = null;
}
下面是題解
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
var former = head,latter = head;
for(var i =0;i<k;i++){
former = former.next;
}
while(former!=null){
former = former.next;
latter = latter.next;
}
return latter
};
其中former代表的是快指針，latter是慢指針，它們的起點(diǎn)相同，都是從鏈表頭部head開(kāi)始，former先走了k個(gè)節(jié)點(diǎn)，然后慢指針latter才開(kāi)始啟動(dòng)，與快指針former同步往后走，這個(gè)差距始終都是k個(gè)節(jié)點(diǎn)。最終，當(dāng)former走完最后節(jié)點(diǎn)，變成null時(shí)，latter就是此完整鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn)了。
這里還有另一種表達(dá)方式，也可以參考，意思是一樣的。
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let fast = head;
let slow = head;
let flag = 0;
while (fast) {
if (flag >= k) {
slow = slow.next;
}
fast = fast.next;
flag ++;
}
return slow;
};
復(fù)雜度分析
時(shí)間復(fù)雜度都是O(n),n為鏈表長(zhǎng)度；空間復(fù)雜度都是O(1)，變量都是常量階的;
參考鏈接:
https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/jskuai-man-zhi-zhen-by-liberhome-dnxt/ https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/