小工具知识网

当前位置: 首页 > 行业知识 > 【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点

行业知识

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

2026-11-17 23:15:17 来源:互联网转载

✅作者���介:热爱后端语言的大学生,CSDN内容合伙人

✨精品专栏:C++面向对象

系列专栏:算法百炼成神

文章目录

  • 前言
  • 1、AB9【模板】链表
    • 1.1、解题思路
    • 1.2、代码实现及注释
    • 2、AB10 ~ AB11题解
      • 2.1、解题思路
      • 2.2、代码实现及注释
      • 3、AB12 删除链表的节点
        • 3.1、解题思路
        • 3.2、代码实现

          前言

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

          1、AB9【模板】链表

          题目链接:点击即可挑战

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


          题目描述:

          1.1、解题思路

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

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

          1.2、代码实现及注释

          本题源码:

          #include 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 > 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         while (ptr) {            cout   public:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {        ListNode* vhead = new ListNode(-1);        ListNode* cur = vhead;        while (pHead1 && pHead2) {            if (pHead1-val 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 删除链表的节点

            题目链接:删除链表节点

            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;    }};

            链表题打牢基础的话,对后续数据结构的理解也有很大帮助,建议大家多多练习,题目旁的链接点进去即可挑战!

上一篇:服务器怎么读取本地磁盘?

下一篇:scgo社区服务器怎么玩?