引言

在上一篇文章中，介紹了反轉(zhuǎn)鏈表
我們利用了鏈表是邏輯連續(xù)的特點(diǎn)，逆置了鏈表的邏輯連接順序，從而實(shí)現(xiàn)反轉(zhuǎn)鏈表：
戳我查看反轉(zhuǎn)鏈表詳解哦

在本篇文章中，我們將介紹找鏈表的中間結(jié)點(diǎn)與鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)：
（由于這兩道題目的思路比較簡單，就放在一起介紹）
鏈表的中間結(jié)點(diǎn)OJ鏈接
鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)OJ鏈接

鏈表的中間結(jié)點(diǎn)

題目描述與思路

這道題要求我們找到鏈表的中間結(jié)點(diǎn)并返回這個(gè)中間結(jié)點(diǎn)。
若鏈表有奇數(shù)個(gè)結(jié)點(diǎn)，返回中間結(jié)點(diǎn)地址；若鏈表有偶數(shù)個(gè)結(jié)點(diǎn)，這個(gè)鏈表就有兩個(gè)中間結(jié)點(diǎn)，返回后一個(gè)。即如果單鏈表有5個(gè)結(jié)點(diǎn)，返回第3個(gè)結(jié)點(diǎn)的地址；若單鏈表有6個(gè)節(jié)點(diǎn)，返回后一個(gè)中間結(jié)點(diǎn)，即第4個(gè)結(jié)點(diǎn)。
函數(shù)的參數(shù)為鏈表第一個(gè)結(jié)點(diǎn)的地址。結(jié)構(gòu)體變量與主函數(shù)部分已經(jīng)定義，我們只需要實(shí)現(xiàn)接口即可。

對(duì)于這道題目，我們當(dāng)然可以先遍歷鏈表，計(jì)算出鏈表的長度，再運(yùn)算出中間結(jié)點(diǎn)是第幾個(gè)。然后再遍歷到該位置并返回即可。
但是這樣的算法顯得有些麻煩，有沒有一種算法可以實(shí)現(xiàn)只遍歷一遍就找到中間結(jié)點(diǎn)呢？

當(dāng)然是可以的：
我們可以采用快慢指針的方法來實(shí)現(xiàn)：快指針一次向前移動(dòng)兩個(gè)結(jié)點(diǎn)；慢指針一次向前移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)快指針到鏈表末尾時(shí)，慢指針的位置就是單鏈表的中間結(jié)點(diǎn)：

實(shí)現(xiàn)

為了使代碼更簡潔，我們可以對(duì)結(jié)構(gòu)體名稱重命名：

typedef struct ListNode ListNode;

要實(shí)現(xiàn)這個(gè)算法，我們首先需要兩個(gè)指針變量fast與slow，將它們都初始化為單鏈表頭結(jié)點(diǎn)的地址：

ListNode* fast = head;
ListNode* slow = head;

然后while循環(huán)，每次循環(huán)中slow向后移動(dòng)一個(gè)結(jié)點(diǎn)；fast向后移動(dòng)兩個(gè)結(jié)點(diǎn)。

當(dāng)fast->next為NULL時(shí)，即fast已經(jīng)不能實(shí)現(xiàn)向后移動(dòng)兩個(gè)結(jié)點(diǎn)了，所以此時(shí)跳出循環(huán)。并且，當(dāng)fast后面兩個(gè)結(jié)點(diǎn)均不為NULL時(shí)，才進(jìn)行向后移動(dòng)的操作，否則跳出循環(huán)。每次循環(huán)，先執(zhí)行slow指針向后移動(dòng)一個(gè)結(jié)點(diǎn)，這樣可以使鏈表長度為偶數(shù)時(shí)，slow指向中間結(jié)點(diǎn)的后一個(gè):

typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) 
{ListNode* fast = head;ListNode* slow = head;while (fast->next){slow = slow->next;if (fast->next->next){fast = fast->next->next;}else{break;}}return slow;
}

鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)

題目描述與思路

這道題要求我們找到單鏈表中的倒數(shù)第k個(gè)結(jié)點(diǎn)。

我們當(dāng)然可以遍歷整鏈表，計(jì)算鏈表的長度。計(jì)算出鏈表的倒數(shù)第k個(gè)元素的位置后，再遍歷找到，并返回。
但是這樣的算法顯得有些麻煩，我們可以嘗試在只遍歷一遍的情況下實(shí)現(xiàn)：

我們可以使用雙指針的方法，先讓快指針向后移動(dòng)k個(gè)結(jié)點(diǎn)。然后兩個(gè)指針一起向后移動(dòng)，當(dāng)快指針t指向最后一個(gè)結(jié)點(diǎn)時(shí)，慢指針就指向鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)。

實(shí)現(xiàn)

為了使代碼更簡潔，我們可以對(duì)結(jié)構(gòu)體名稱重命名：

typedef struct ListNode ListNode;

要實(shí)現(xiàn)這個(gè)算法，我們首先需要兩個(gè)指針變量fast與slow，將它們都初始化為單鏈表頭結(jié)點(diǎn)的地址：

ListNode* fast = pListHead;
ListNode* slow = pListHead;

首先判斷k是否為0與鏈表是否為空，如果是，則直接返回NULL；

然后將fast指針向后移動(dòng)k-1個(gè)結(jié)點(diǎn)，若fast在向后移動(dòng)時(shí)，fast為NULL說明鏈表的長度小于k-1，此時(shí)返回NULL。我們可以通過在循環(huán)之后對(duì)fast指針進(jìn)行判斷，從而得知循環(huán)是否因鏈表長度不足而結(jié)束。

如果不是，則進(jìn)入循環(huán)，slow指針與fast指針同時(shí)向前移動(dòng)，當(dāng)fast指針指向鏈表的最后一個(gè)結(jié)點(diǎn)時(shí)，slow指向的就是倒數(shù)第k個(gè)元素，返回slow即可。
需要注意的是，此時(shí)要求fast指針在鏈表最后一個(gè)結(jié)點(diǎn)時(shí)停下，所以while的判斷雕件為fast->nex，而不是fast：

typedef struct ListNode ListNode;struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{ListNode* fast = pListHead;ListNode* slow = pListHead;if (k == 0 || pListHead == NULL){return NULL;}while (--k != 0 && fast != NULL)//--k為條件時(shí)，循環(huán)k-1次{fast = fast->next;}if (fast == NULL){return NULL;}else{while (fast->next){slow = slow->next;fast = fast->next;}}return slow;
}

總結(jié)

當(dāng)然，這只是其中一種方法，相信還有別的思路。歡迎大家在評(píng)論區(qū)討論

還有幾道關(guān)于單鏈表的題目講解，歡迎持續(xù)關(guān)注哦

如果大家認(rèn)為我對(duì)某一部分沒有介紹清楚或者某一部分出了問題，歡迎大家在評(píng)論區(qū)提出

如果本文對(duì)你有幫助，希望一鍵三連哦

希望與大家共同進(jìn)步哦