数据结构——链表——找中间结点、倒数第K个结点、删除倒数第K个结点(C语言版)(要求只能遍历一次链表)

时间:2021-05-12 11:23:28

由于要进行期末考试了,所以就将明天的提前发了,留一点复习的时间!!

这次的题是在只进行一次遍历链表的情况下,找到中间结点;或者找到倒数第K个结点,当明白了这两个问题的思想之后,最后的删除倒数第K个结点就只是调用一下之前的函数了!

这儿有个趣味小问题:一百米赛跑,兔子的速度是乌龟的两倍,那么兔子到终点后,乌龟的位置在哪儿??问题很显然,乌龟就在五十米处,也就是整个赛道的中间点

由此可见:遍历一次链表,设置一个跑得快的快指针,和一个跑的慢的慢指针,快指针的速度是慢指针的两倍,那么问题就解决了!

具体怎么实现呢?如图:
1、空链表直接返回
2、一个结点的链表也直接返回头结点
3、多个结点,则采用快慢指针的方法,最后达到找到middle结点的效果

数据结构——链表——找中间结点、倒数第K个结点、删除倒数第K个结点(C语言版)(要求只能遍历一次链表)

代码如下:

PNode FindMiddleNode(PNode pHead)
{
    assert(pHead);                           //参数检测

PNode pFast;                             //设置 快慢指针
PNode pSlow;

if (NULL == pHead)
{
    printf("链表为空,无中间结点!!\n");
    return NULL;
}

if (NULL == pHead->_pNext)                                    //只有一个结点 直接返回头结点
    return pHead;

pFast = pHead;
pSlow = pHead;

while (pFast->_pNext->_pNext)               // 遍历链表  快指针一次走两步,慢指针一次走一步
{
    pFast = pFast->_pNext->_pNext;        
    pSlow = pSlow->_pNext;
    if (NULL == pFast->_pNext)
        return pSlow;
}

return pSlow;                                      //返回慢指针
}

类似的方法:将快指针走两倍慢指针的方式稍作改变:快指针先走K步,然后快慢指针以相同的速度一起走,当快指针走到NULL的时候,慢指针正好走到倒数第K个结点

如图:K先走两步,在同时走,达到找倒数第K个结点的目的!!
数据结构——链表——找中间结点、倒数第K个结点、删除倒数第K个结点(C语言版)(要求只能遍历一次链表)

代码如下:

PNode FindLastKNode(PNode pHead, int K)
{
    assert(pHead);                                   //参数检测

PNode pFast = pHead;
PNode pSlow = pHead;

if (NULL == pHead)                               //空链表 
{
    printf("链表为空,找不到该结点!!\n");
    return NULL;
}

while (pFast)
{
    while (K)                                  //快指针 先走 K 步
    {
        if (NULL == pFast)                               //链表的结点数 小于 K    找不到倒数第 K 个结点
        {
            printf("倒数第 %d 结点不存在!\n", K);
            return NULL;
        }
        pFast = pFast->_pNext;
        --K;
    }
    pFast = pFast->_pNext;                           //快指针先走 K 步 之后   快慢指针 以相同速度一起走
    pSlow = pSlow->_pNext;
}

return pSlow;
}

很简单,找到了上面两个题的思路之后,对于删除倒数第K个结点,我们只需要调用以上函数即可:

代码如下:

void DeleteLastKNode(PNode pHead, int K)
{
    assert(pHead);                                         //参数检测

PNode pDelet = FindLastKNode(pHead, K);                //找到倒数 K 结点 用到了一次遍历链表

if (NULL == pDelet->_pNext)                            //此结点为尾结点,直接删除并且赋空
{
    free(pDelet);
    pDelet = NULL;
}
else                                                    //此结点为非尾结点,调用函数删除   无遍历链表操作
{
    DeleteListNotTailNode(pDelet);
}

}

其中调用了删除非尾结点函数,对于这个函数,我的上一篇CSDN有详细的解题过程和思路:
链接如下:https://blog.csdn.net/code_zx/article/details/80580316
最后:献上测试函数以及测试结果
测试函数:

void testListFindAndDelet()
{
    PNode pHead;
    PNode pos;

SListInit(&pHead);

PNodePushBack(&pHead, 1);
PNodePushBack(&pHead, 2);
PNodePushBack(&pHead, 3);
PNodePushBack(&pHead, 4);
PNodePushBack(&pHead, 5);
printSList(pHead);

pos = FindMiddleNode(pHead);
DeleteListNotTailNode(pos);
printSList(pHead);

pos = FindLastKNode(pHead, 2);
DeleteListNotTailNode(pos);
printSList(pHead);

DeleteLastKNode(pHead, 2);
printSList(pHead);

}

测试结果:首先尾插1,2,3,4,5;然后找到中间结点并且删除得到:1,2,4,5;再找到倒数第二个结点删除得到:1,2,5;最后删除倒数第二个结点得到:1,5;
数据结构——链表——找中间结点、倒数第K个结点、删除倒数第K个结点(C语言版)(要求只能遍历一次链表)
欢迎访问,谢谢支持!!