数据结构刷题训练——链表篇（一）（上）-阿里云开发者社区

数据结构刷题训练——链表篇（一）（上）

2023-10-16 53

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构刷题训练——链表篇（一）

前言

今天我将开启一个新的专栏，数据结构与算法刷题训练营，题目从基础简单题目开始逐步进阶，以便于初学者巩固和运用所学的知识。

题目一：链表的中间节点

题目描述：

示例与提示：

题目链接

思路

题目中的链表属于单链表，我们要怎么计算中间节点呢？先遍历一遍链表统计链表节点个数，然后计算出中间节点，再遍历到需要返回的节点。这或许是大多数人能想到的方法。但是这种方法效率太低。今天我向大家介绍一种新的做题思路，这种方法在其他题目中也是适用。

快慢指针法：

我们可以创建两个指针，一个快指针一次走两步，一个慢指针一次走一步。当快指针走到尾时，返回慢指针就是中间节点。

分析

情况一：

节点为奇数个。

假设节点有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. }