目录
1.链表的中间节点
2.链表中倒数第k个节点
1.链表的中间节点
思路1：遍历链表，统计节点个数count，返回第count/2 +1个节点
📖Note:注意循环条件为--mid，--mid循环执行mid-1次，mid--循环mid次，返回的是中间节点的下一个节点
struct ListNode* middleNode(struct ListNode* head){struct ListNode* cur = head;int count = 0;//统计节点个数while(cur){count++;cur = cur->next;}//返回第count/2+1个节点cur = head;int mid = count/2 + 1;while(--mid){cur = cur->next;}return cur;}思路二：快慢指针
设置一个慢指针slow，一个快指针fast，慢指针一次走一步，快指针一次走两步
需要分两种情况：链表节点个数为奇数个和节点个数为偶数个
1️⃣奇数个的情况
当链表节点个数为奇数个时，可以发现，快指针fast->next == NULL时，遍历结束，此时慢指针slow刚好指向中间节点
2️⃣偶数个的情况：
当链表节点个数为偶数个时，可以发现，快指针fast == NULL时，遍历结束，此时慢指针slow刚好指向中间节点
综上：遍历结束的条件为fast == NULL或fast->next == NULL
参考代码如下：
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head;struct ListNode* slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}2.链表中倒数第k个节点
与上题思路二相似的还有下例
分析：
输出链表中倒数第k个节点，假设有一个指针指向链表尾节点的next，即指向NULL，我们从这个节点向前看，尾节点相对这个指针来说是第一个节点，相对链表头指针head来说便是倒数第一个节点，对于倒数第k个节点，指向这个节点的指针和指向NULL的指针始终相差的是k个节点；设置一个快指针fast，一个慢指针slow，fast指针先走k步，slow指针不动，此时fast指针和slow指针就相差k个节点，然后slow指针和fast指针同时向后走，直到fast指针指向NULL，此时slow指向的节点就是倒数第k个节点
以输出倒数第三个节点为例，步骤如下图：
🌸特殊情况讨论：
1️⃣空链表：返回空指针
2️⃣倒数第一个
由上图可以发现，输出倒数第一个节点的逻辑与输出倒数的k个节点的逻辑相同
3️⃣倒数第N个（链表长度为N）
由上图可以发现，输出倒数第N个节点的逻辑与输出倒数的k个节点的逻辑相同
4️⃣k=0或k>N（N为链表的长度）
- k=0时，输出链表的倒数第0个节点，应该为空
此时fast指针和slow指针都不会发生变化，，所以
- k>N时，fast先走k步会发生空指针的访问
在fast指针向后走k步的过程中，需要随时检查fast指针的有效性，如果fast==NULL,直接返回空指针即可
参考代码如下：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* slow = pListHead,*fast = pListHead;if(pListHead){while(k--){if(fast == NULL){return fast;}fast = fast->next;}while(fast){slow = slow->next;fast = fast->next;}}return slow;}
