鏈表中倒數(shù)第k個節(jié)點
輸入一個鏈表粱快，輸出該鏈表中倒數(shù)第k個節(jié)點清笨。為了符合大多數(shù)人的習慣脆诉，本題從1開始計數(shù)雾棺，即鏈表的尾節(jié)點是倒數(shù)第1個節(jié)點卸夕。例如柱告，一個鏈表有6個節(jié)點截驮，從頭節(jié)點開始，它們的值依次是1际度、2葵袭、3、4乖菱、5坡锡、6蓬网。這個鏈表的倒數(shù)第3個節(jié)點是值為4的節(jié)點。
來源：力扣（LeetCode）
題解
- 方法一:常規(guī)方法
首先想到的方法是先循環(huán)遍歷得到鏈表的長度n鹉勒，然后再循環(huán)n-k次獲得倒數(shù)第k個節(jié)點帆锋。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
int len=0;
struct ListNode *ptr = head;
while(ptr)
{
len++;
ptr=ptr->next;
}
int j=len-k;
while(head && j>0)
{
j--;
head=head->next;
}
return head;
}
- 方法二：雙指針
倒數(shù)第k個節(jié)點，可以理解成距離最后一個節(jié)點（這里可以認為是NULL）隔了k個節(jié)點禽额。
所以可以用兩個相隔k個節(jié)點的指針同步移動锯厢，當前面的指針移動到尾部時，后面的指針
剛好到距離前面指針k個節(jié)點的位置脯倒。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
struct ListNode *former=head;
struct ListNode *latter=head;
while(former!=NULL)
{
former=former->next;
if(k>0){
k--;
}else{
latter=latter->next;
}
}
return latter;
}
