当前位置：首页 > news >正文

链表的中间结点与链表的倒数第k个结点（精美图示详解哦）

news 2025/7/13 2:43:35

全文目录

引言
链表的中间结点
- 题目描述与思路
- 实现
链表的倒数第k个结点
- 题目描述与思路
- 实现
总结

引言

在上一篇文章中，介绍了反转链表
我们利用了链表是逻辑连续的特点，逆置了链表的逻辑连接顺序，从而实现反转链表：
戳我查看反转链表详解哦

在本篇文章中，我们将介绍找链表的中间结点与链表的倒数第k个结点：
（由于这两道题目的思路比较简单，就放在一起介绍）
链表的中间结点OJ链接
链表的倒数第k个结点OJ链接

链表的中间结点

题目描述与思路

在这里插入图片描述
这道题要求我们找到链表的中间结点并返回这个中间结点。
若链表有奇数个结点，返回中间结点地址；若链表有偶数个结点，这个链表就有两个中间结点，返回后一个。即如果单链表有5个结点，返回第3个结点的地址；若单链表有6个节点，返回后一个中间结点，即第4个结点。
函数的参数为链表第一个结点的地址。结构体变量与主函数部分已经定义，我们只需要实现接口即可。

对于这道题目，我们当然可以先遍历链表，计算出链表的长度，再运算出中间结点是第几个。然后再遍历到该位置并返回即可。
但是这样的算法显得有些麻烦，有没有一种算法可以实现只遍历一遍就找到中间结点呢？

当然是可以的：
我们可以采用快慢指针的方法来实现：快指针一次向前移动两个结点；慢指针一次向前移动一个结点。当快指针到链表末尾时，慢指针的位置就是单链表的中间结点：

实现

为了使代码更简洁，我们可以对结构体名称重命名：

typedef struct ListNode ListNode;

要实现这个算法，我们首先需要两个指针变量fast与slow，将它们都初始化为单链表头结点的地址：

ListNode* fast = head;
ListNode* slow = head;

然后while循环，每次循环中slow向后移动一个结点；fast向后移动两个结点。

当fast->next为NULL时，即fast已经不能实现向后移动两个结点了，所以此时跳出循环。并且，当fast后面两个结点均不为NULL时，才进行向后移动的操作，否则跳出循环。每次循环，先执行slow指针向后移动一个结点，这样可以使链表长度为偶数时，slow指向中间结点的后一个:
在这里插入图片描述

typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) 
{ListNode* fast = head;ListNode* slow = head;while (fast->next){slow = slow->next;if (fast->next->next){fast = fast->next->next;}else{break;}}return slow;
}

链表的倒数第k个结点

题目描述与思路

在这里插入图片描述
这道题要求我们找到单链表中的倒数第k个结点。

我们当然可以遍历整链表，计算链表的长度。计算出链表的倒数第k个元素的位置后，再遍历找到，并返回。
但是这样的算法显得有些麻烦，我们可以尝试在只遍历一遍的情况下实现：

我们可以使用双指针的方法，先让快指针向后移动k个结点。然后两个指针一起向后移动，当快指针t指向最后一个结点时，慢指针就指向链表的倒数第k个结点。

实现

为了使代码更简洁，我们可以对结构体名称重命名：

typedef struct ListNode ListNode;

要实现这个算法，我们首先需要两个指针变量fast与slow，将它们都初始化为单链表头结点的地址：

ListNode* fast = pListHead;
ListNode* slow = pListHead;

首先判断k是否为0与链表是否为空，如果是，则直接返回NULL；

然后将fast指针向后移动k-1个结点，若fast在向后移动时，fast为NULL说明链表的长度小于k-1，此时返回NULL。我们可以通过在循环之后对fast指针进行判断，从而得知循环是否因链表长度不足而结束。

如果不是，则进入循环，slow指针与fast指针同时向前移动，当fast指针指向链表的最后一个结点时，slow指向的就是倒数第k个元素，返回slow即可。
需要注意的是，此时要求fast指针在链表最后一个结点时停下，所以while的判断雕件为fast->nex，而不是fast：
在这里插入图片描述

typedef struct ListNode ListNode;struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{ListNode* fast = pListHead;ListNode* slow = pListHead;if (k == 0 || pListHead == NULL){return NULL;}while (--k != 0 && fast != NULL)//--k为条件时，循环k-1次{fast = fast->next;}if (fast == NULL){return NULL;}else{while (fast->next){slow = slow->next;fast = fast->next;}}return slow;
}