目录
链表的中间节点
链表中倒数第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 here if(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; }
