前言
今天我将开启一个新的专栏，数据结构与算法刷题训练营，题目从基础简单题目开始逐步进阶，以便于初学者巩固和运用所学的知识。
题目一：链表的中间节点
题目描述：
示例与提示：
题目链接
思路
题目中的链表属于单链表，我们要怎么计算中间节点呢？先遍历一遍链表统计链表节点个数，然后计算出中间节点，再遍历到需要返回的节点。这或许是大多数人能想到的方法。但是这种方法效率太低。今天我向大家介绍一种新的做题思路，这种方法在其他题目中也是适用。
快慢指针法：
我们可以创建两个指针，一个快指针一次走两步，一个慢指针一次走一步。当快指针走到尾时，返回慢指针就是中间节点。
分析
情况一：
节点为奇数个。
假设节点有5个，那需要返回的节点就是第3个节点。初始时，两指针都指向第一个节点，慢指针一次走一步，快指针一次走两步。执行一次情况如上图。当快指针走到最后一个节点时就要结束如下图：
情况二：
节点为偶数个。
这是已经执行两次后的状态，接下来fast指针继续走：
fast指向NULL，而slow指向要返回的节点。
题解
了解完整体思路，我们依据分析中的情况进行编写代码：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast=pListHead,*slow=pListHead; for(int i=0;i<k;i++) { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }
题目二：链表中倒数第k个结点
题目描述：
题目链接
思路
这道题目依然可以使用快慢指针的方法来寻找倒数第k个节点。先让快指针走k步，然后让两指针同时向后移动，知道快指针遍历完链表结束。
分析
初始情况下，两指针都指向第一个节点，先让fast指针走k步：
我们假设要找倒数第3个节点，fast走3步就指向了第四个节点。
然后两指针开始同时移动：
当fast指针指向NULL时就结束，此时slow指向的就是倒数第k个节点。
题解
根据上述的分析，我们进行编写代码：
1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { 2. struct ListNode* fast=pListHead,*slow=pListHead; 3. 4. 5. for(int i=0;i<k;i++) 6. { 7. if(fast==NULL) 8. { 9. return NULL; 10. } 11. fast=fast->next; 12. } 13. while(fast) 14. { 15. fast=fast->next; 16. slow=slow->next; 17. } 18. return slow; 19. }
在代码实现时要注意特殊情况，如果链表为NULL或者k大于链表长度，传进来就要进行特殊处理。
题目三：合并两个有序链表
题目描述：
示例：
题目链接：
思路
题目中给的是升序数组，解题思路就是比较链表元素，取小的进行尾插。思路较为简单。
分析
接下来我们对整体规划进行分析假设初始时：
把一个链表的元素插入到另一个链表这样操作太麻烦，所以我们可以重新创建一个头指针，将两个链表上的节点插入到新的链表中，创建新链表时，初始化头和尾都为NULL。
然后进行比较，第一步两个大小相同，任取一个插入：
然后再拿着list2中的第一个节点与list1节点进行比较，插入：
以此类推不断进行比较尾插。
结束条件就是一个链表为NULL结束
最后将剩余节点的链表尾插到新链表中，返回新链表的头。
