【初阶数据结构】——leetcode:链表的中间结点

1. 题目介绍

链接: link

我们一起来看一下题目:
在这里插入图片描述
题目给我们一个链表,要求我们返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。

2. 思路分析——快慢指针

题目其实挺简单的,但是我们比较容易想到的都是比较暴力的解法:

比如我们可以先遍历一遍求出链表的长度,然后求出中位数,再遍历寻找并返回对应的结点。

那我们来加一点挑战性,如果要求只能遍历一遍,要如何解决呢?

那么比较经典的一种思路就是快慢指针。
大致的思路是这样的:
定义两个“指针”:快指针fast,慢指针slow。两个指针都从第一个结点开始往后走,慢指针一次走一步,快指针一次走两步,这样快指针走到终点的时候,慢指针刚好就在中间位置。

那具体我们来画图分析一下:
那这里要分为两种情况:链表结点的个数为奇数个或者为偶数个。
首先来看如果是奇数个,比如:

在这里插入图片描述
fast和slow都从第一个结点开始。
fast一次走两步,slow一次走一步
在这里插入图片描述
我们看到这样最终fast走到结尾的时候(即fast->next==NULL),slow就正好处在链表的中间结点。

那如果结点的个数是偶数呢?

在这里插入图片描述
像这样。
我们再来画一下:
在这里插入图片描述
我们发现如果是奇数个,fast最后正好可以走到最后一个结点的位置;而如果是偶数的话,fast就走到最后一个结点的下一个,就是NULL。(即fast==NULL时结束)
而此时slow的位置也是正确的,因为题目要求如果有两个中间结点,则返回第二个中间结点。
我们看到slow正好处在第二个中间结点。

3. 代码实现

那我们来实现一下代码:

在这里插入图片描述
在这里插入图片描述
没问题,通过了。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow=head;
    struct ListNode* fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }

    return slow;
}

4. 思维拓展

刚才这道题目中要求如果两个中间结点的话(那就是偶数个结点),要返回的是第二个中间结点。

那我们上面的快慢指针的思路fast一次走两步,刚好偶数个的话,fast会停在最后一个结点的下一个位置(即fast==NULL时结束),此时slow刚好指向第二个中间结点。

那么,如果我现在要求偶数个的话,返回第一个中间结点,怎么做呢?

如果是这样的话比较简单的一个思路就是可以再增加一个指针prev,记录slow指针的前一个结点。
在这里插入图片描述
这样的话如果最终是fast为空,那就是偶数个,我们就返回prev(就是第二个中间结点),如果是fast->next为空,那就是奇数个,还是返回slow。

相关推荐

  1. 数据结构:第9关:删除中满足区间值

    2024-04-01 14:54:02       30 阅读

最近更新

  1. MyEclipse tomcat debug 断点看不到变量值

    2024-04-01 14:54:02       0 阅读
  2. MAC 终端命令

    2024-04-01 14:54:02       0 阅读
  3. 2024年5月软考高项冲刺复习攻略,稳过!

    2024-04-01 14:54:02       0 阅读
  4. 树的遍历算法题总结(第二十六天)

    2024-04-01 14:54:02       0 阅读
  5. sqlalchemy expunge的简单使用

    2024-04-01 14:54:02       0 阅读

热门阅读

  1. gitee创建仓库后的基本指令

    2024-04-01 14:54:02       5 阅读
  2. python面试题(51~60)

    2024-04-01 14:54:02       5 阅读
  3. 学习总结!

    2024-04-01 14:54:02       5 阅读
  4. fpga_awb

    fpga_awb

    2024-04-01 14:54:02      6 阅读
  5. Day1 - Hive基础知识

    2024-04-01 14:54:02       5 阅读
  6. 在Debian 11上安装GCC

    2024-04-01 14:54:02       5 阅读
  7. static修饰的方法为什么不能被覆盖?

    2024-04-01 14:54:02       6 阅读
  8. leetcode93.复原IP地址

    2024-04-01 14:54:02       5 阅读