【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #

前言

• 对于单链表的OJ练习，需要深刻理解做题的思路，这样我们才能够在任何场景都能够熟练的解答有关链表的问题。

• 关于OJ练习（1）：-> 传送门 <-，其题目较为简单，思路也好理解，本章与（1）差不多，难度不大，核心点就在于理解解题思路。

---

链表的中间结点

题目链接：-> 传送门 <-。

• 该题目描述为：给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

1.如果节点数为奇数，这个中间节点就显而易见了。（3）

2.如果节点数为偶数，这里认为中间两个节点的第二个节点为中间节点。（4）

思路一：

• 我们可以先遍历一遍链表，统计一下链表节点的个数。

• 然后将这个个数除以二加一（count / 2 + 1）便是中间这个节点的位置。

• 当然，我们在循环寻找这个中间节点的时候，是从头节点开始的，因此循环只需要循环（（count / 2 + 1） - 1）即可。

代码实现：

struct ListNode* middleNode(struct ListNode* head){struct ListNode* cur = head;int count = 0;while (cur){count ++ ;cur = cur->next;}count = count / 2 + 1;while (-- count) // 循环count - 1次{head = head->next;}return head;
}

思路二：

• 该做法为快慢指针。

• 啥为快慢指针呢？在本题有关当中，我们定义两个指针指向链表的头节点，并且共同遍历链表，不同的是，一个指针每一次走两步，另一个指针每次走一步，这就是快慢指针。

• 每当快指针满足循环结束条件，慢指针都是指向链表的中间节点的。因为快指针走两步，慢指针走一步，整个移动的位移差相差一倍，所以每当快指针满足结束条件的时候，慢指针走的步数都是快指针走的步数的一半， 因此慢指针指向的那个节点就是整个链表的中间节点。

• 快指针结束的条件有两种情况，一种是快指针刚好指向空结束，一种是快指针指向尾节点结束，也就是快指针的next为NULL。

1.当快指针刚好指向NULL结束，此时链表的节点个数为偶数：

2.当快指针指向尾节点结束，也就是快指针的next为NULL，此时链表的节点个数为奇数：

代码实现：

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

注意：
while循环的判断条件，fast一定要在前面，这是因为：判断是从左到右判断的，如果fast->next在前，而此时链表的结点的个数为偶数，那么fast就会直接到达NULL，这时候对空指针解引用操作就出问题了。

---

链表中倒数第k个结点

题目链接：-> 传送门 <-。

• 该题目描述为：输入一个链表，输出该链表中倒数第k个结点。。

思路一：

• 既然是倒数第k个，那我们就看看是正数的第几个。

• 先遍历一遍单链表，统计一下链表的结点个数（count），通过数学知识，可得倒数的第k个结点就是正数的第count - k + 1个节点，这时只要在遍历一次链表，找到第count - k + 1个节点返回即可。

• 当然，这里嘚注意k是不是大于链表节点的个数的情况。

代码实现：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* cur = pListHead;int count = 0;// 统计链表节点的个数while (cur){count ++ ;cur = cur->next;}// 如果k大于链表的节点个数，直接返回NULLif (k > count) return NULL;int tmp = count - k;// 由于从头个节点开始算，因此只需要循环count - k次就可以找到倒数第k个节点while (tmp -- ){pListHead = pListHead->next;}return pListHead;
}

思路二：

• 同样是快慢指针，这里的快慢指针解法是：快指针先向后走k步或者先向后走k - 1步，然后快指针与慢指针同时向后走，当快指针满足循环结束条件停止，此时慢指针指向的节点就是倒数第k个节点。

1.如果快指针先向后走k步，此时快指针与慢指针之间相差k步，因此，当快指针到达NULL时，此时慢指针刚好指向倒数第k个节点。（倒数第k个节点与NULL相差k步）(循环结束条件：fast == NULL)

2.如果快指针先向后走k - 1步，此时快指针与慢指针之间相差k - 1步，然后快指针与慢指针同时向后走，当快指针满足循环结束条件停止，此时慢指针指向的节点就是倒数第k个节点。（倒数第k个节点与尾节点相差k - 1步）（循环结束条件：fast->next == NULL）

代码实现：(这里只实现fast先走k步的情况，fast先走k - 1的情况大同小异)

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow = pListHead, * fast = pListHead;// fast先走k步while (k -- ){if (!fast) return NULL; // 如果k还没为0但fast已经指向空了，说明k大于链表的结点的个数，此时直接返回NULLfast = fast->next;}// 当fast为NULL时结束循环while (fast){fast = fast->next;slow = slow->next;}return slow;
}

---

写在最后

对于单链表的题目练习，最重要的是思路，我们在数据结构阶段要养成画图的习惯，因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。

感谢阅读本小白的博客，错误的地方请严厉指出噢！