目录

• 链表的中间节点
• 链表中倒数第k个结点

链表的中间节点

OJ链接：链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

这里，最容易想起的一个方法就是：先遍历一遍链表，得出链表长度，再遍历出这个链表的中间节点

其实还有一个更妙的方法，就是使用快慢指针 ：

定义slow指针和fast指针
slow一次走一步，fast一次走两步

假设当前链表个数是奇数个：

过程如下：

可以看到，当fast移动到最后时，slow的位置恰好是中间节点：

所以就可以得，其代码的循环条件为fast->next!=NULL

假设当前链表个数是偶数个：

过程如下：
同样可以发现：
最后当fast为空时，，slow指向中间节点，所以对于偶数个节点的链表来说，循环条件是fast!=NULL

所以，代码如下：

struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow,*fast;slow = fast = head;while(fast&&fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}

链表中倒数第k个结点

OJ链接：链表中倒数第k个结点

描述:
输入一个链表，输出该链表中倒数第k个结点。

示例1
输入： 1,{1,2,3,4,5}
返回值：{5}

这道题的思路是：
倒数第k个节点，距最后一个节点的距离是k-1
所以可以先让fast指针移动k-1步，之后slow和fast一起移动，每次移动一步，直到fast->next==NULL
先让fast指针移动k步，之后slow和fast一起移动，每次移动一步，直到fast==NULL

过程如下：

代码如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code hereif(pListHead==NULL){return NULL;}struct ListNode* slow,*fast;slow = fast = pListHead;while(k--){if(fast==NULL){return NULL;}fast = fast->next;}while(fast){fast = fast->next;slow = slow->next;}return slow;
}