链表经典算法OJ题目

这篇具有很好参考价值的文章主要介绍了链表经典算法OJ题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.单链表相关经典算OJ题目1:移除链表元素

链表经典算法OJ题目,链表,算法,数据结构

思路一

直接在原链表里删除val元素,然后让val前一个结点和后一个节点连接起来。

这时我们就需要3个指针来遍历链表:

pcur  —— 判断节点的val值是否于给定删除的val值相等

prev ——保存pcur的前一个节点,为删除节点后,连接pcur之后的节点做准备

del —— 保存pcur之后的一个节点,为删除节点之后,连接链表做准备,和继续遍历链表

那么一开始它们的位置应该怎么放呢?

链表肯定是从第一个节点开始遍历的,那么 pcur 肯定就指向第一个节点,del可以先不给值,等到要删除的时候在把pcur之后的节点赋值给它

prev是在pcur前面的一个节点,我们会发现,当第一次遍历时,pcur前面并没有节点,那么我们就创造一个节点:哨兵卫(Sentinel),于链表连接,再让prev指向它。之后我们在返回新的链表的时候,我们返回 哨兵卫(Sentinel)的下一个节点即可。

链表经典算法OJ题目,链表,算法,数据结构

链表经典算法OJ题目,链表,算法,数据结构

代码 :

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建哨兵卫节点并于链表连接
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next = head;

    ListNode* prev = newhead;
    ListNode* pcur = head;
    ListNode* del;

    当我们pcur走到尾节点指向的NULL处时停止循环
    while(pcur)
    {
        //当符合给定的val值,删除
        if(pcur->val == val)
        {
            del = pcur->next;   //记录pcur下一个节点位置
            free(pcur);         //删除pcur节点
            prev->next = del;   //将pcur前后的节点连接起来
            pcur = del;         //走向下一个节点
            
        }

        //当不符合给定的val值,继续遍历链表
        else
        {      
            prev = pcur;
            pcur = pcur->next;
        }
    }

    //释放不要的哨兵卫节点并返回新的链表
    ListNode* p = newhead->next;
    free(newhead);

    return p;
}

 思路二

直接创建一个新的链表,遍历原链表,将不是val值的节点尾插到新的链表中

需要用到两个指针:

pcur —— 用来遍历原链表,找不是val值的节点

ptail —— 新链表的尾节点,将来尾插至此节点后面

链表经典算法OJ题目,链表,算法,数据结构

代码:

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建哨兵卫节点,这里是为了防止对NULL指针解引用。
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next =  NULL;

    ListNode* newtail,* pcur;
    newtail = newhead;
    pcur = head;
    
    //当pcur走到原尾节点->NULL时停止循环
    while (pcur)
    {
        //如果和给定的val值节点不相等,则尾插至新链表中
        if (pcur->val != val)
        {
            newtail->next = pcur;
            newtail = newtail->next;
        }
        pcur = pcur->next;    //pcur继续遍历原链表
    }

    newtail->next = NULL;  //出了循环之后,记得把新的链表的尾节点指向NULL,保证不会带出多余节点

    //释放哨兵卫节点
    ListNode* p = newhead->next;
    free(newhead);

    return p;
}

 2.单链表相关经典算OJ题目2:反转链表

链表经典算法OJ题目,链表,算法,数据结构

思路一

创建一个新的链表,将原链表的节点依次拿到新链表进行头插

需要两个指针:

pcur —— 遍历原链表

newhead —— 作为新链表的第一个节点

链表经典算法OJ题目,链表,算法,数据结构

代码:

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {

    //如果链表为NULL则不用反转
    if(head == NULL)
        {
            return head;
        }

    ListNode* newhead = NULL;
    ListNode* pcur = head;
    ListNode* Transfer = NULL;
    
    //开始反转
    while(pcur)
    {
        Transfer = pcur;   // 保存当前节点的指针
        pcur = pcur->next; // 移动到下一个节点

        Transfer->next = newhead;  // 反转当前节点的next指针,指向新的头节点
        newhead = Transfer;   // 更新新链表的头节点
    }

    return newhead;
}

思路二

创建三个指针,完成链表的反转:

n1 : 记录n2前一个节点

n2 : 用来遍历链表

n3 : 记录n2后一个节点

链表经典算法OJ题目,链表,算法,数据结构

代码:

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    
    //链表为NULL时不用反转

    if (head == NULL) {
        return head;
    }

    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = n2->next;

    当n2遍历完链表时循环停止
    while (n2)
    {

        n2->next = n1;   //让n2节点指向n1节点
        n1 = n2;         //让n1走至下一个节点
        n2 = n3;         //让n2走至下一个节点

      // 因为n3比n2快一步,当n2走至尾节点的时候,n3已经为NULL了,不处理的话会造成NULL的解引用
        if (n3 != NULL)   
            n3 = n3->next;   //让n3走至下一个节点
    }

    //当循环结束时n1会成为新的第一个节点
    return n1;
    
}

 3.单链表相关经典算OJ题目3:链表的中间节点

链表经典算法OJ题目,链表,算法,数据结构

思路 

这一题说难也不难,相信想一下大部分的码农都可以写出来

这里我就介绍一个更妙的方法:快慢指针法

什么是快慢指针法?顾名思义,就是创造两个指针,一个指针走的慢一点,一个指针走的快一点,对应到我们这一题上就是,同一时间内,一个指针走一步,一个指针走两步:2 × slow = fast

那么它是否可以应对题目给出的条件呢?当中间节点有两个时,返回第二个中间节点

两个中间节点

链表经典算法OJ题目,链表,算法,数据结构

单中间节点

 链表经典算法OJ题目,链表,算法,数据结构

可以看见无论是双中间节点 还是 单中间节点这个方法都可以完美解决,我们也可以观察出循环的结束条件为:当 fast 指针为NULL 或 fast指针下一个节点为NULL时停止

代码:

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    
    //创建快慢指针
    ListNode *slow,*fast = NULL;
    
    链表不为NULL时快慢指针从第一个节点开始遍历
    if(head != null);
    slow = fast = head;

    //当 fast 指针为NULL 或 fast指针下一个节点为NULL时停止
    //这两个表达式位置不可以换,若换,当fast为NULL时会出现对NULL指针解引用
    //如果换,当fast为NULL时,第一个表达式为假,第二个表达式就不执行了,不会出现NULL指针解引用
    while(fast != NULL && fast->next)
    {
        slow = slow->next;        //慢指针走一个节点
        fast = fast->next->next;  //快指针走两个节点
    }

    return sl
}

  4.单链表相关经典算OJ题目4:合并两个有序数组

 链表经典算法OJ题目,链表,算法,数据结构 

思路 

创建新链表,并且通过遍历两个原来的链表比较大小来添加至新的链表中

代码:

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {

    //设置哨兵节点当新链表的第一个节点
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next = NULL;
    ListNode* newtail = newhead; //只有一个节点,第一个节点 = 尾节点

    //创建l1 l2 指针遍历原链表list1 list2
    ListNode* l1 = list1;
    ListNode* l2 = list2;

    //当遍历完一个链表时,循环停止,不可能出现两个链表同时遍历完的情况
    while(l1 != NULL && l2 != NULL)
    {
        
        //l1 或 l2 指向的值,小的放入新链表,并让其指针l1或l2 与 newtail指针往后走
        if(l1->val < l2->val)
        {
            newtail->next = l1;
            l1 = l1->next;
            newtail = newtail->next;
        }
        else
        {
            newtail->next = l2;
            l2 = l2->next;
            newtail = newtail->next;
        }
    }

    //将没有遍历完的链表,将其内的元素一次性插入新链表中
    if(l1 != NULL)
    {
        newtail->next = l1;
    }
    else
    {
        newtail->next = l2;
    }

    //存储哨兵卫后面的节点,并释放哨兵卫节点
    ListNode* p = newhead->next;
    free(newhead);
    
    return p;    //返回新的头节点
}

  5.单链表相关经典算OJ题目5:环形链表的约瑟夫问题

链表经典算法OJ题目,链表,算法,数据结构

思路

利用我们的环形链表,依次的去遍历链表,使用count计数器计数,当count = m时删除节点,当环形链表只剩一个节点(这个节点下一个节点指向自己)时,就说明找到了最后留下的人。

这时我们需要用到两个指针:

pcur —— 遍历环形链表

prev —— 保存pcur的前一个节点,为删除节点做准备

链表经典算法OJ题目,链表,算法,数据结构

代码:

typedef struct ListNode ListNode;

//创建新节点
ListNode* Buynode(int x){
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p->val = x;
    p->next = NULL;
    return p;
}

//创建环形链表
ListNode* creatCircle(int n){


    ListNode* head,*ptail;    
    head = Buynode(1);      //创建第一个节点val值为1
    ptail = head;

    for(int i = 2;i <= n;i++)     //继续创建节点,直到节点数 = n ,从第一个节点val = 1
    {                             //第二个 = 2....一直到n个节点,其val = n
        ptail->next = Buynode(i);
        ptail = ptail->next;
    }

    // 让链表的头尾相连
    ptail->next = head;

    //因为要用到第一个节点的上一个节点,所以返回ptail
    return ptail;
}


int ysf(int n, int m ) {

    ListNode* prev,*pcur;    //创建所需要的指针

    prev = creatCircle(n);   //创建环形链表
    pcur = prev->next;       //pcur从没有相连的第一个节点开始遍历
    int count = 1;           //创建计数器

    //开始循环,当环形链表中的节点指向自己时,说明只剩一个节点,循环结束
    while(pcur->next != pcur)
    {

        //如果计数器 == m 则删除该节点
        if(count == m)
        {
            prev->next = pcur->next;  //prev->next指向需删除节点的下一个节点
            free(pcur);               //删除该节点
            pcur = prev->next;        //pcur走向已删除节点的下一个节点
            count = 1;                //重置计数器
        }

        //如果计数器 != m 则删除该节点
        else
        {
            prev = pcur;            //两个指针都走向各自的下一个节点
            pcur = pcur->next;
            count++;                //计数器++
        }
    }

    
    return pcur->val;     //返回最后一个节点的val值
}

    6.单链表相关经典算OJ题目 6 :分割链表

链表经典算法OJ题目,链表,算法,数据结构

思路一 

修改原链表,把小于特定的 x 值尾插到链表后面

pcur —— 遍历链表直到原尾节点

prev —— pcur的前一个节点,为了删除节点准备

patil —— 原尾节点

newpatil —— 新的尾节点

newhead —— 一个哨兵节点作为新的头节点

链表经典算法OJ题目,链表,算法,数据结构

代码:

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){

    //如果链表尾为NULL则不用分割
    if(head == NULL)
    {
        return head;
    }

    //创建哨兵卫并于链表第一个节点连接,让它成为新的第一个节点
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next = head;

    //分割链表需要用到的指针
    ListNode* prev,*pcur,*ptail,*newptail;
    prev = newhead;
    pcur = head;

    //找尾节点
    while(pcur->next != NULL)
    {
        pcur = pcur->next;
    }
    ptail = pcur;
    newptail = pcur;
    pcur = head;   //pcur重新回到原第一个节点

    //当pcur遍历到原尾节点的时候停止循环
    while(pcur != ptail)
    {

        //如果节点的val值比x大,则把节点尾插至链表
        if(pcur->val >= x)   
        {
           prev->next = pcur->next;      //先让prev的下一个节点指向pcur下一个节点
           newptail->next = pcur;       //pcur节点尾插至链表后
           newptail = newptail->next;  //新的尾节点
           pcur = prev->next;         //让pcur走到prev指向的下一个节点
        }

        //否者pcur与prev各自往后走一个节点
        else
        {
            prev = pcur;
            pcur = pcur->next;
        }
    }

    newptail->next = NULL;断绝尾节点后面还带着其它节点

    
    ListNode* p = newhead->next;
    free(newhead);
    

    return p;
}

思路二

创建一个新的链表,把大于等于x的节点尾插到新的链表中,小于x的节点头插至链表中

链表经典算法OJ题目,链表,算法,数据结构

 代码:

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)
    {
        return head;
    }
    
    //新链表起码要有一个节点,不然不知道是头插还是尾插
    ListNode* newhead,*pcur,*newptail,*del;
    newhead = newptail = pcur = head;   //把原链表的第一个节点给到新链表
                                        //这时新链表 头 = 尾 

    pcur = del = pcur->next;   //pcur走到原链表的第二个节点

    //当pcur走到NULL时说明已经遍历完原链表
    while(pcur)
    {

        //尾插
        if(pcur->val >= x)
        {
            if(del)                     //怕出现NULL指针解引用
            del = pcur->next;          //存储pcur下一个节点,不然待会找不到
            newptail->next = pcur;     //让新链表尾节点指向pcur
            newptail = newptail->next;   //更习新链表的尾节点
            pcur = del;                 //pcur走向下一个节点
        }

        //头插
        else
        {
            if(del)                    //怕出现NULL指针解引用
            del = pcur->next;          //存储pcur下一个节点,不然待会找不到
            pcur->next = newhead;      //pcur的这个节点头插至新链表第一个节点处
            newhead = pcur;            //更新新链表的第一个节点
            pcur = del;                 //pcur走向下一个节点
        }

    }

    //让新链表的尾节点指向NULl,防止有别的节点被带上
    newptail->next = NULL;

    return newhead;
}

思路三:

创建 一大  一小 两个链表 ,把大于等于点放到大链表中,小于x的节点放到小链表中,当原链表的节点被全部放置完毕,把大链表链接到小链表后面。

链表经典算法OJ题目,链表,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-858834.html

 代码:

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){

    //链表为NULL直接返回链表
    if(head == NULL)
    {
        return head;
    }

    //创建大链表的第一个节点,和尾节点
    ListNode* Bnewhead,*Bnewptail;
    Bnewhead = Bnewptail = (ListNode*)malloc(sizeof(ListNode));
    
    //创建小链表的第一个节点,和尾节点
    ListNode* Snewhead,*Snewptail;
    Snewhead = Snewptail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* pcur = head;   //遍历原链表指针
    while(pcur)
    {

        //尾插至大链表
        if(pcur->val >= x)
        {
            Bnewptail->next = pcur;       //将大于等于x的pcur节点尾插至大链表
            Bnewptail = Bnewptail->next;  //更新大链表尾节点
        }

        //尾插至小链表
        else
        {
            Snewptail->next = pcur;       //将小于x的pcur节点尾插至小链表
            Snewptail = Snewptail->next;   //更新小链表尾节点
            
        } 
        pcur = pcur->next;              //让pcur继续遍历原链表下一个节点
    }
    Bnewptail->next = NULL;     //让大链表的尾节点的下一个节点指向NULL防止它带出其他节点
    Snewptail->next = Bnewhead->next;   //让小链表的尾节点的下一个节点指向大链表的第一个节点

    //释放动态申请的空间
    ListNode* ret= Snewhead->next;   //存储大小合并后的链表的第一个有效节点
    free(Bnewhead);                 
    free(Snewhead);
    Bnewhead = Snewhead = NULL;

    //返回新链表
    return ret;
    
}

到了这里,关于链表经典算法OJ题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构与算法】手撕链表OJ题

    给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 思路一 :一种比较普遍的方式,边遍历边找不同。我们可以通过定义两个指针,一个指向头节点,一个置为NULL。当遇到值为相同的时候,直接跳过去。指向下一位

    2024年02月10日
    浏览(45)
  • 【数据结构与算法】一套链表 OJ 带你轻松玩转链表

    ✨个人主页:bit me ✨当前专栏:数据结构 ✨刷题专栏:基础算法   简介: 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例2: 输入:head = [], val =

    2024年01月22日
    浏览(48)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(45)
  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(87)
  • 数据结构课程设计题目——链表综合算法设计、带头双向循环链表、插入、显示、删除、修改、排序

      课程设计题目1–链表综合算法设计   一、设计内容   已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不

    2024年02月08日
    浏览(64)
  • 数据结构——链表OJ题

    目录   1.给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 3.变形题:找到链表中倒数第k个

    2024年02月21日
    浏览(41)
  • 【数据结构】二叉树的相关操作以及OJ题目

    当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因

    2024年03月19日
    浏览(50)
  • 【数据结构】栈与队列经典oj题

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   栈两种线性表示都能实现

    2024年02月03日
    浏览(42)
  • 二叉树经典OJ题——【数据结构】

    W...Y的主页  😊 代码仓库分享 💕  今天我们来进行二叉树的OJ练习,就是利用二叉树的前序、中序、后续以及晨序遍历的特性进行OJ训练。话不多说,来看我们的第一道题。 【leetcode 965.单值二叉树】 OJ链接  如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二

    2024年02月07日
    浏览(46)
  • 【数据结构初阶】链表OJ

    OJ 方案一: 题目解析: 方案二: 题目解析:把原链表遍历一遍,插入新链表 OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: 定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交 OJ 题目解析: OJ 题目解析:

    2024年02月05日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包