1. 链表的中间节点
链接：876. 链表的中间结点
描述：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例2:：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
思路1：
第一种思路是 暴力求解 。
题目不是要求链表的中间节点吗？那么我遍历链表，直接算出链表的长度。
对于奇数个节点，那么我返回 长度 / 2的节点当然没问题，且题目要求，如果有两个中间节点，则返回第二个中间节点。那不正好，我偶数个节点时 长度 / 2 就是中间第二个节点，这不就秒了吗(doge)。
但是如果只能遍历一遍呢？我们能用什么方法解决？看思路2↓
思路2(精讲)：
这里采用的思路为快慢指针。
方法是这样的，给定一个慢指针 slow 一次走一步，快指针 fast 一次走两步。快指针的速度是慢指针的2倍。
当链表的节点数为 奇数 时，快指针走到链表 最后一个节点 停止；当链表的节点数为 偶数 时。快指针走到 空指针 停止。
最后返回的 slow 就是中间节点。
这里的原理其实就是利用了一个差值的原理，当快指针走完链表，那么慢指针恰好走了它的一半，它们走的时间一样，那么慢指针就是中间节点的位置。
2. 链表中倒数第k个结点
链接：链表中倒数第k个结点
描述：
输入一个链表，输出该链表中倒数第k个结点。
示例1:：
输入：
1,{1,2,3,4,5}
返回值：
{5}
思路1：
和求链表的中间节点的方法相似，为直接法。
要求链表的倒数第 k 个节点，那么就是删除链表正数第 len(链表长度) - k + 1 个节点。
举个例子，例如链表长度为 5，删除倒数第 2 个节点，就是删除链表正数第 4 个节点，推导出来就是第 len + 1 - k 个节点。
所以只要先算出链表长度，然后遍历到 len + 1 - k 个节点返回即可。
但是这里需要注意一下区间和迭代关系。
既然这道题目也可以用直接法，那么能否也适用于快慢指针？这当然可以，而且这道题的方法也很巧妙，接下来看思路2↓
思路2(精讲)：
又是奇妙的快慢指针，这里大体是这样一个方案。
给定一个快指针 fast 和一个慢指针 slow。
我们要求链表倒数第 k 个节点，那么我们就先让快指针走 k 步。
然后让 fast 和 slow 一起走，当 fast 走到空指针，这时 slow 为倒数第 k 个节点。
注意：如果在 fast 走 k 步的过程中，fast 迭代为了空指针，这时直接返回空指针。
那么这里的原理是什么呢？
其实就是首先让 fast 走 k 步，让 fast 和 slow 的间隔为 k。链表的倒数第 k 个节点，就是正数 len + 1 - k 个节点，那么当我 fast 走到空指针后，链表走完，那么现在 fast 走的距离就相当于链表的长度 + 1，fast 和 slow的间隔为 k ，那么现在的 slow 就为正数 len + 1 - k个节点，这时返回 slow就是倒数第 k 个节点。
代码：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast, *slow; fast = slow = pListHead; if (pListHead == NULL) return NULL; // fast 先走 k 步 while (k--) { // 放置 fast 先走到空 if (fast == NULL) { return NULL; } fast = fast->next; } // 迭代 while (fast) { slow = slow->next; fast = fast->next; } return slow; }
3. 链表分割
链接：CM11 链表分割
描述：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路：
题目要求我们将小于 x 的节点和大于等于 x 的节点分隔，小于 x 的节点在前，大于等于 x 的节点在后，且不能改变原来的数据顺序。
不能改变顺序就比较棘手，如果没有这个条件，我们可以用双指针来写。但是题目既然给出了要求，我们就得想办法解决。
我们创建一个新链表存放小于 x 的值，另一个存放大于等于 x 的值。然后遍历原链表，将符合条件的值放入对应的链表中，最后再将存放小于 x 的值的链表和存放大于等于 x 的值的链表链接起来。
那么这过程肯定是尾插，本题使用哨兵位是十分合适的，因为本题有很多的空指针处理的情况，所以我们设定两个哨兵位 lessHead 、 greaterHead。
再给定两个尾lessTail 、 greaterTail，用来尾插。 但是最后记得要释放哨兵位。
请注意，如果以 greaterHead 结束的元素不是链表的最后一个元素(即原链表最后一个元素小于 x )，就可能会造成 链表带环 的情况，需要断开环，然后将 greaterTail 的 next 置为空。同样的，过会也会画图来讲解。
代码：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode* lessTail, *lessHead, *greaterTail, *greaterHead; // 建立哨兵位 lessTail = lessHead = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterTail = greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = pHead; while (cur) { if (cur->val < x) { lessTail->next = cur; lessTail = cur; } else { greaterTail->next = cur; greaterTail = cur; } cur = cur->next; } // 链接两个链表 lessTail->next = greaterHead->next; greaterTail->next = NULL; // 断开环 // 拷贝节点，释放哨兵位 struct ListNode* ans = lessHead->next; free(lessHead); free(greaterHead); return ans; } };
这道题目不用哨兵位也可以做，但是比较考验细节，思路大体差不多，有兴趣可以去试试，下面给出截图和代码：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode* lessTail, *lessHead, *greaterHead, *greaterTail; lessTail = lessHead = greaterHead = greaterTail = NULL; struct ListNode* cur = pHead; while (cur) { if (cur->val < x) { if (lessTail == NULL) { // 第一次尾插 lessHead = lessTail = cur; } else { // 第一次尾插 lessTail->next = cur; lessTail = lessTail->next; } cur = cur->next; } else { if (greaterTail == NULL) { greaterHead = greaterTail = cur; } else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } } // lessHead 为空，说明原链表为空或链表的值全大于 x // 且链表尾部的 next 一定为空 // 返回 greaterHead if (lessHead == NULL) return greaterHead; // 如果 lessHead 和 greaterHead 都不为空 // 说明正常分割 // 将其链接，greaterHead 尾部链空 if (lessHead != NULL && greaterHead != NULL) { lessTail->next = greaterHead; greaterTail->next = NULL; } // 无论是正常分割，还是链表的值全小于 x // 都是返回 lessHead return lessHead; } };
