LeetCode算法实战:链表元素剔除与反转操作

LeetCode 算法实践:链表元素移除与反转操作

第一题 - 移除链表元素

方法一 - 原地删除

思路阐述:要实现链表中指定值元素的删除,需分情况处理。一是头节点的值恰好为目标值,此时直接删除头节点并更新头指针;二是中间或尾部节点的值为目标值,需借助前驱节点来完成删除操作。

解题步骤
- 删除头部目标节点:通过循环判断头节点是否存在且值是否等于目标值。若满足条件,先临时保存头节点,将头节点更新为下一个节点,再释放临时保存的头节点。
- 删除中间和尾部目标节点:初始化临时指针temp指向新的头节点,遍历链表时确保当前节点及其下一个节点非空。若下一个节点的值等于目标值,临时保存该节点,将当前节点的next指针指向其下下个节点,然后释放临时保存的节点;若下一个节点的值不等于目标值,将temp指针后移。
- 返回新头节点:遍历结束后,返回更新后的头节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    while (head != NULL && head->val == val) 
    {
        struct ListNode* tmp = head;
        head = head->next;
        free(tmp);
    }
    struct ListNode* temp = head;
    while (temp != NULL && temp->next != NULL)
     {
        if (temp->next->val == val)
        {
            struct ListNode* cur = temp->next;
            temp->next = cur->next;
            free(cur);
        } 
        else 
        {
            temp = temp->next;
        }
    }
    return head;
}

复杂度分析
- 时间复杂度:O(n),需遍历链表的每个节点一次。
- 空间复杂度:O(1),仅使用常数级额外空间存储指针变量。

方法二 - 双指针

思路剖析:利用双指针prevcur遍历链表,当遇到值为目标值的节点时,调整指针跳过该节点并释放内存。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while (cur != NULL) 
    {
        if (cur->val != val) 
        {
            prev = cur;
            cur = cur->next;
        } 
        else 
        {
            if (cur == head && cur->val == val) 
            {
                head = cur->next;
                free(cur);
                cur = head;
            } 
            else 
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
    }
    return head;
}

代码分析
- 初始化双指针prev初始化为NULL,用于记录当前节点的前一个节点;cur初始化为头节点head,用于遍历链表。
- 遍历链表:通过while循环遍历链表,直到所有节点处理完毕。
- 处理当前节点:若当前节点值不等于目标值,更新prev并后移cur;若当前节点值等于目标值,根据是否为头节点分别处理,调整指针并释放内存。
- 返回头指针:遍历结束后,返回更新后的头指针。

方法三 - 尾插

思路讲解:遍历原链表,将不等于目标值的节点依次尾插到新链表中,最后返回新链表的头指针。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;
    while (cur) 
    {
        if (cur->val != val) 
        {
            // 尾插
            if (tail == NULL) 
            {
                newhead = tail = cur;
            } 
            else 
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        } 
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if(tail)
    {
        tail->next=NULL;
    }
    return newhead;
}

代码分析
- 初始化变量cur用于遍历原链表,初始化为原链表头headnewhead为新链表头指针,初始化为NULLtail为新链表尾指针,初始化为NULL,用于高效尾插节点。
- 遍历原链表:通过while循环遍历原链表,处理每个节点。
- 处理当前节点:若当前节点值不等于目标值,根据新链表是否为空进行尾插操作;若当前节点值等于目标值,释放该节点并继续遍历。
- 处理尾节点指针:遍历结束后,确保新链表尾节点的next指针为NULL
- 返回新链表头指针:返回新链表的头指针。

第二题 - 反转链表

描述:给定单链表的头节点head,将链表反转并返回反转后的链表。

方法一 - 迭代

思路解析:使用三个指针协同工作,逐步将每个节点的next指针指向前驱节点,实现链表反转。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* tmp = head;
    while(tmp!=NULL)
    {
        tmp = n2->next;
        n2->next=n1;
        n1=n2;
        n2=tmp;
    }
    return n1;
}

代码分析
- 初始化指针n1初始化为NULL,指向当前处理节点的前驱节点;n2初始化为头节点head,指向当前正在处理的节点;tmp初始化为头节点head,作为临时指针保存后续节点。
- 遍历链表:通过while循环确保遍历完整链表。
- 反转操作:保存后继节点,调整当前节点的next指针指向前驱节点,然后移动指针继续处理。
- 返回新头节点:循环结束后,n1指向原链表最后一个节点,即反转后的新头节点,返回n1

方法二 - 采用头插创建新链表

思路剖析:遍历原链表,为每个节点创建副本,将副本节点依次插入新链表头部,形成原链表的逆序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL; //新链表的头指针
    while (cur) 
    {
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        if (newNode == NULL) 
        {
            perror("malloc failed");
            // 释放已分配的节点
            while (newHead) 
            {
                struct ListNode* temp = newHead;
                newHead = newHead->next;
                free(temp);
            }
            return NULL;
        }
        newNode->val = cur->val;
        newNode->next = newHead; //头插法:新节点指向当前头
        newHead = newNode;       //更新头指针
        cur = cur->next;
    }
    return newHead; //返回新链表的头结点
}

代码分析
- 初始化变量cur指向原链表当前节点,初始化为headnewHead为新链表头指针,初始化为NULL
- 遍历原链表:通过while循环遍历原链表,为每个节点创建副本。
- 头插操作:将副本节点插入新链表头部,更新新链表头指针。
- 错误处理:若内存分配失败,释放已创建的新链表节点并返回NULL
- 返回结果:遍历结束后,返回新链表的头指针。

总结

至此,对链表相关操作的探索暂告一段落,但编程之路才刚刚起步。编写代码是与计算机逻辑深度交互的过程,虽会在结构设计和算法实现中遇到挑战,但这些经历能加深对代码逻辑和数据组织的理解。愿你在编程之路上持续探索,书写属于自己的精彩篇章,期待下次与你在代码世界中再度相逢,见证你的成长与进步。

文章整理自互联网,只做测试使用。发布者:Lomu,转转请注明出处:https://www.it1024doc.com/12853.html

(0)
LomuLomu
上一篇 14小时前
下一篇 10小时前

相关推荐

  • 【最新破解方法】IDEA 2025.1永久激活码分享 – 零基础小白也能轻松搞定

    作为Java开发者的首选IDE,IntelliJ IDEA凭借其出色的代码智能分析、自动补全和强大的调试功能赢得了众多程序员的喜爱。不过,正版的IDEA价格不菲,对于学生党和个人开发者来说是一笔不小的开支。今天就给大家带来一个简单易行的IDEA 2025.1版本永久激活方法,亲测有效! 我注意到网上有很多激活教程,但大多数都已失效或操作复杂。经过多次尝试,我…

    2025 年 4 月 28 日
    1.7K00
  • 2024年主流使用的JDK版本及其核心特性介绍

    原文全文详见个人博客:https://www.coderli.com/feature-of-popular-jdk-version/2024年主流使用的JDK版本及其核心特性介绍在群里交流的时候,经常遇到不同同学使用的JDK版本五花八门,并且很多不知道其使用版本的特点。作为Java开发者,理解不同JDK版本的核心特性和优势不仅能提高我们的开发效率,还能帮助我…

    2024 年 12 月 28 日
    44200
  • 2025年最新DataGrip激活码及永久破解方法(支持2099年)

    JetBrains全系列工具完美破解指南 今天为大家带来一个超实用的技术分享,适用于DataGrip、PyCharm、IDEA等JetBrains系列开发工具的永久激活方案。先展示效果图,可以看到我的DataGrip已经成功激活至2099年! 下面将详细介绍DataGrip的完整激活流程,该方法同样兼容旧版本,无论您使用Windows、MacOS还是Linu…

    DataGrip激活码 4天前
    2500
  • 【Java多线程】如何使用Java多线程下载网络文件 断点续传

    如何使用Java多线程下载网络文件,并实现断点续传 在现代网络应用中,多线程下载是一种常见的技术,它可以显著提高下载速度并提供更好的用户体验。本篇文章将介绍如何使用Java实现多线程下载,并结合项目中的代码作为示例进行讲解。 1. 多线程下载的基本原理 多线程下载的基本思想是将一个文件分成多个部分,每个部分由一个线程独立下载,最后将这些部分合并成完整的文件。…

    未分类 2025 年 1 月 13 日
    26700
  • IDEA PyCharm激活教程 – 使用破解补丁永久激活

    本教程适用于PyCharm 2025、IDEA、DataGrip、Goland等Jetbrains产品,支持全家桶激活!无论您使用的是Windows、Mac还是Linux,均可按照本教程成功激活PyCharm 2025至2095年。 激活截图展示 首先,我们来展示一下最新版本的PyCharm 2025破解成功的截图,如下所示,您可以看到已经成功激活至2095…

    IDEA破解教程 2025 年 4 月 22 日
    19400

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信