【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点

这篇具有很好参考价值的文章主要介绍了【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

✅作者简介:热爱后端语言的大学生,CSDN内容合伙人
✨精品专栏:C++面向对象
🔥系列专栏:算法百炼成神

🔥前言

本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面试真题,面试、找工作完全可以来这里找机会。此外,网站内的编码主题多样化,调试功能可运用性强,可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗,快去注册开启算法百炼成神之路吧!

1、AB9【模板】链表

题目链接:点击即可挑战

考查链表的设计,插入,删除操作,做的时候考虑链表尾部的特殊处理,锻炼思维能力


题目描述:

ab9 【模板】链表,# 经典算法的C++实现,链表,算法,数据结构,c++ab9 【模板】链表,# 经典算法的C++实现,链表,算法,数据结构,c++

1.1、解题思路

对于模板链表题,只需按照平常学习的知识构建普通单向有头结点的链表即可:

  1. insertdelete方法都需要判断链表中是否有值为x的结点,那么可以单独写一个函数来判断
  2. 对于插入和删除操作我都是采用的两个移动指针的方法:ptr在前,pre在后
  3. 对于此题来说最后不能输出空格,因此要加条件限制

1.2、代码实现及注释

本题源码:

#include <iostream>
using namespace std;

struct list {
    int data;
    list* next;
};

bool judge(list* &L, int x) {
    list* ptr = L->next;
    while (ptr) {
        if (ptr->data == x)
            return true;
        else
            ptr = ptr->next;
    }
    return false;
}

int main() {
    list* L = (list*)malloc(sizeof(list));
    L->next = NULL;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "insert") {
            list* ptr = L->next;
            list* pre = L;
            int x, y;
            cin >> x >> y;
            list* e = (list*)malloc(sizeof(list));
            e->next = NULL;
            e->data = y;
            if (judge(L, x)) {
                while (ptr) {
                    if (ptr->data == x) {
                        pre->next = e;
                        e->next = ptr;
                        break;
                    } else {
                        pre = ptr;
                        ptr = ptr->next;
                    }
                }
            } else {
                while (pre->next) {
                    pre = pre->next;
                }
                pre->next = e;
            }
        } else if (s == "delete") {
            int x;
            cin >> x;
            list* ptr = L->next;
            list* pre = L;
            if (judge(L, x)) {
                while (ptr) {
                    if (ptr->data == x) {
                        if (ptr->next) {
                            pre->next = ptr->next;
                            ptr = NULL;
                            free(ptr);
                            break;
                        } else {
                            pre->next = NULL;
                            ptr = NULL;
                            free(ptr);
                            break;
                        }
                    } else {
                        pre = ptr;
                        ptr = ptr->next;
                    }
                }
            }
        }
    }
    list* ptr = L->next;
    if (ptr == NULL) cout << "NULL";
    else {
        while (ptr) {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
}

重要注释:

  • judge函数返回一个布尔类型,为true则链表存在x,为false则不存在x
  • 对于insert操作:
    • 若存在x, 指针preptr逐步遍历,直到ptr指向结点的值为x,将新结点e添加到链表中
    • 若不存在x,让pre指针循环后移到最后一个结点位置,然后将e插入到pre指向的结点后
  • 对于delete操作:
    • 在存在x的情况下,判断其是否在链表的末尾:
      • 若不在链表末尾:让pre指向ptr的下一个结点,删除并释放ptr
      • 若在链表末尾:直接删除并释放ptr指针即可
    • 若不存在x,不进行任何操作
  • 最后就是对链表的内容进行输出:注意输出空格的时候要再链表非末尾的情况下进行

2、AB10 ~ AB11题解

题目链接:合并两个排序链表

ab9 【模板】链表,# 经典算法的C++实现,链表,算法,数据结构,c++

2.1、解题思路

  • 新创建一个链表,根据已知的两个递增链表的元素大小来升序的在新链表中存储数据
  • 头插法建表,使用另外的链表指针作为辅助
  • 当两个已知链表有一个已经遍历完时,直接让辅助指针指向非空的链表结点即可

2.2、代码实现及注释

本题源码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* vhead = new ListNode(-1);
        ListNode* cur = vhead;
        while (pHead1 && pHead2) {
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        cur->next = pHead1 ? pHead1 : pHead2;
        return vhead->next;
    }
};

重要注释:

  • new ListNode(-1) 相当于创建了一个头结点,cur作为头插的赋值指针
  • while循环内部为头插法建立升序链表的过程
  • 三目运算符目的是让新链表的尾指向剩余链表的头
  • 最后返回的时候不需要头结点,因此结果为vhead->next

反转链表解析的博文地址:反转链表及进阶

反转链表的题目中我用了vector容器自带的reverse方法,非常适合入门新手

3、AB12 删除链表的节点

题目链接:删除链表节点

ab9 【模板】链表,# 经典算法的C++实现,链表,算法,数据结构,c++

3.1、解题思路

观察链表的定义代码可知,该题链表是没有头结点的,那么就可以分情况讨论:

  1. 若链表第一个结点的值为目标值,直接返回结点的下一个指向即可
  2. 若链表首结点不是目标值,将其当作头结点即可,使用两个移动指针的方法:
    • 步骤与本文上面 模板链表 步骤几乎一致,不做赘述

3.2、代码实现

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param val int整型
     * @return ListNode类
     */
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* ptr = head->next;
        if(head->val==val) return ptr;
        ListNode* pre = head;
        while (ptr) {
            if (ptr->val == val) {
                if (ptr->next) {
                    pre->next = ptr->next;
                    break;
                } else {
                    pre->next = NULL;
                }
            } else {
                pre = ptr;
                ptr = ptr->next;
            }
        }
        return head;
    }
};

链表题打牢基础的话,对后续数据结构的理解也有很大帮助,建议大家多多练习,题目旁的链接点进去即可挑战!文章来源地址https://www.toymoban.com/news/detail-583172.html

到了这里,关于【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【代码随想录 | Leetcode | 第六天】链表 | 反转链表 | 两两交换链表中的节点 | 删除链表的倒数第 N 个结点

    欢迎来到小K的Leetcode|代码随想录|专题化专栏,今天将为大家带来反转链表、两两交换链表中的节点和删除链表的倒数第N个节点的分享 ✨ ✨题目链接点这里 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 1: 示例 2: 示例 3: 提示: 链表中节点的数

    2024年02月16日
    浏览(55)
  • Java 算法篇-链表的经典算法:有序链表去重、合并多个有序链表

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍         文章目录          1.0 链表的说明          2.0 有序链表去重的实现方式         2.1 有序链表去重(保留重复的节点) - 使用递归来实现         2.2 有序链表去重(保留重复的节点) - 使用双指针

    2024年02月05日
    浏览(44)
  • 【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】

    题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1, 2, 4], l2 = [1, 3, 4] 输出:[1, 1, 2, 3, 4, 4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 我们的思路是,先定义

    2023年04月24日
    浏览(46)
  • 【C++】STL 算法 - 排序算法 ( 合并排序算法 - merge 函数 | 随机排序算法 - random_shuffle 函数 | 反转序列算法 - reverse 函数 )

    在 C++ 语言 的 标准模板库 ( STL , STL Standard Template Library ) 中 , 提供了 merge 合并排序算法函数 用于 将 两个已排序好的容器 合并成一个新的已排序的容器 ; merge 合并排序算法 函数原型 如下 : 参数解析 : InputIterator1 first1 参数 : 有序 输入 容器 1 的 迭代器范围 的 起始迭代器 (

    2024年01月18日
    浏览(48)
  • 面试算法78:合并排序链表

    输入k个排序的链表,请将它们合并成一个排序的链表。 用k个指针分别指向这k个链表的头节点,每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步,再比较k个指针指向的节点并选取值最小的节点。重复这个过程,直到所有节点都被选取出来

    2024年02月03日
    浏览(38)
  • 算法刷题-链表-删除链表的倒数第N个节点

    力扣题目链接 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 进阶:你能尝试使用一趟扫描实现吗? 示例 1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:head = [1,2], n = 1 输出:[1] 双指针的经典应用,

    2024年02月08日
    浏览(42)
  • 【数据结构和算法】删除链表的中间节点

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 三、代码 四、复杂度分析 这是力扣的 2095 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。 慢慢开始链表的模块了

    2024年01月19日
    浏览(74)
  • 【算法Hot100系列】删除链表的倒数第 N 个结点

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月04日
    浏览(41)
  • 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

    /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* reverseList(ListNode* head) {              } };

    2024年02月22日
    浏览(49)
  • 算法基础模板 快排、快选、归并、二分、离散化、区间合并、链表、图搜索、最短路等

    解决逆序对数量问题,即 if arr[i]arr[j]:res += mid - i + 1 时间复杂是 O ( n 2 + m ) O(n2+m) O ( n 2 + m ) , n n n 表示点数, m m m 表示边数 时间复杂度 O ( m l o g n ) O(mlogn) O ( m l o g n ) , n n n 表示点数, m m m 表示边数

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包