数据结构——单链表OJ题

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

数据结构——单链表OJ题,数据结构,数据结构,链表


前言

在前面的博客中我们知道了什么是单链表以及如何建立单链表!
现在让我们来检验一下学习成果吧!

提示:此博客中题目均来自牛客网以及力扣网!在题目中我会附带两大网站的链接,大家也可以去练习一下!
若有链接问题可以在评论区及时反馈!


一、删除链表中等于给定值 val 的所有节点

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表

提示:
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

struct ListNode* removeElements(struct ListNode* head, int val) {
     struct ListNode* newhead = NULL;
     struct ListNode* move = head;
     struct ListNode* tail = NULL;

     while (move != NULL) {
         if (move->val != val) {
             if (tail == NULL) {//如果newnode为NULL,则tail等于newnode,则直接将结点地址赋予tail
                 newhead = tail = move;
                 move = move->next;
             }
             else {
                 tail->next = move;
                 move = move->next;
                 tail = tail->next;
             }
         }
         else {
             struct ListNode* temp = move;//新建结点保存要free的地址,以免free后造成节点丢失
             move = move->next;
             free(temp);
         }
     }
     if (tail)//如果新链表不为空,则将其尾结点的next置空
         tail->next = NULL;
     return newhead;
 }

二、反转一个单链表

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* move1 = head;
    struct ListNode* tail = head;
    if (head == NULL || head->next == NULL) {//如果链表为空或者只有一个结点,则不需要反转
        return tail;
    }
    struct ListNode* move2 = move1->next;
    while (move2) {
        struct ListNode* temp = move2->next;//保存下一个结点的地址,防止后面的节点丢失
        move2->next = move1;
        move1 = move2;
        move2 = temp;
    }
    tail->next = NULL;//尾结点的next置空
    struct ListNode* newhead = move1;//move1最后指向了反转链表的起始结点
    return newhead;
}

三、返回链表的中间结点

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表

提示:
链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*move1=head;
    struct ListNode*move2=head;
    while(move2!=NULL&&move2->next!=NULL){//此处move2!=NULL和move2->next!=NULL
        move1=move1->next;                //的位置不能交换,否则会造成空指针错误
        move2=move2->next->next;
    }
    return move1;
}

四、输出该链表中倒数第k个结点

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表
思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    
    struct ListNode*move1=pListHead;
    struct ListNode*move2=pListHead;
    int i=k;
    while(i>0&&move2!=NULL){//move2向后移动k位
        move2=move2->next;
            i--;
    }
    if(move2==NULL&&i>0){//如果k大于链表结点数目,则返回NULL
        return move2;
    }
    while(move2){
        move1=move1->next;
        move2=move2->next;
    }
    return move1;
}

五、将两个有序链表合并

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    struct ListNode*move1=list1;
    struct ListNode*move2=list2;
    struct ListNode*newnode=NULL;
    struct ListNode*tail=NULL;
    while(move1!=NULL&&move2!=NULL){
        if(move1->val<=move2->val){
            if(tail==NULL){{//如果newnode为NULL,则tail等于newnode,则直接将结点地址赋予tail
            newnode=tail=move1;
            move1=move1->next;
            }
            else{
                tail->next=move1;
                move1=move1->next;
                tail=tail->next;
            }
        }
        else{
            if(tail==NULL){//如果newnode为NULL,则tail等于newnode,则直接将结点地址赋予tail
                newnode=tail=move2;
                move2=move2->next;
            }
            else{
                tail->next=move2;
                move2=move2->next;
                tail=tail->next;
            }
            }
    }
    if(move1==NULL){//如果链表1遍历完而链表2没有,则将链表2剩余结点尾插到newnode中
        while(move2!=NULL){
            if(tail==NULL){//如果newnode为NULL,则tail等于newnode,则直接将结点地址赋予tail
                newnode=tail=move2;
                move2=move2->next;
            }
            else{
                tail->next=move2;
                move2=move2->next;
                tail=tail->next;
            }
        }
    }
      if(move2==NULL){//如果链表2遍历完而链表1没有,则将链表1剩余结点尾插到newnode中
        while(move1!=NULL){
           if(tail==NULL){//如果newnode为NULL,则tail等于newnode,则直接将结点地址赋予tail
            newnode=tail=move1;
            move1=move1->next;
            }
            else{
                tail->next=move1;
                move1=move1->next;
                tail=tail->next;
            }
        }
    }
      return newnode;
}

六、链表的回文结构

题目链接:OJ链接

数据结构——单链表OJ题,数据结构,数据结构,链表
思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

bool chkPalindrome(struct ListNode* A) {
    struct ListNode* move1 = A;
    struct ListNode* move2 = A;
    struct ListNode* move3 = A;
    struct ListNode* newnode = NULL;
    struct ListNode* tail = NULL;
    while (move2 != NULL&&move2->next != NULL ) {//找到中间节点
        move1 = move1->next;
        move2 = move2->next->next;
    }
    if (move2 == NULL);//如果节点个数为奇数,则move1向后移动一位
    else {
        move1 = move1->next;
    }
    while (move1 != NULL) {//将后半段链表头插到newnode中
        if (newnode == NULL) {
            newnode = tail = move1;
            move1 = move1->next;
            tail->next = NULL;
        }
        else {
            struct ListNode* temp = move1->next;
            move1->next = newnode;
            newnode = move1;
            move1 = temp;
        }
    }
    struct ListNode* cmp = newnode;
    while (move3 != NULL && cmp != NULL) {//比较原链表前半段和newnode是否相同
        if (move3->val != cmp->val) {
            return 0;
        }
        else {
            move3 = move3->next;
            cmp = cmp->next;
        }
    }
    return 1;
}

七、将链表分割成两部分

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表
思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

ListNode* partition(ListNode* pHead, int x) {
        struct ListNode*head1=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode*head2=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode*tail1=head1;
        struct ListNode*tail2=head2;
        struct ListNode*move=pHead;
        while(move){
            if(move->val<x){
                tail1->next=move;
                move=move->next;
                tail1=tail1->next;
            }
            else{
                tail2->next=move;
                move=move->next;
                tail2=tail2->next;
            }
            }
        tail2->next=NULL;//将尾指针的next置空
        tail1->next=head2->next;
        struct ListNode*temp1=head1;
        struct ListNode*temp2=head2;
        head1=head1->next;//指针指向头结点的下一节点
        free(temp1);//释放掉创建的头结点
        free(temp2);
        return head1;
    }

八、找出第一个公共结点

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

注意:
函数返回结果后,链表必须 保持其原始结构 。

思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *move1=headA;
    struct ListNode *move2=headB;
    int len1=1,len2=1;
    while(move1){//得到链表A的长度
        move1=move1->next;
        len1++;
    }
    while(move2){//得到链表B的长度
        move2=move2->next;
        len2++;
    }
    int k=abs(len1-len2);//取相减的绝对值
    struct ListNode *moveA=headA;
    struct ListNode *moveB=headB;
    if(len1>len2){//较长的链表走k步
        while(k--){
            moveA=moveA->next;
        }
    }
      if(len1<len2){
        while(k--){
            moveB=moveB->next;
        }
    }
      while(moveA&&moveB){
        if(moveA==moveB)
            return moveA;//若地址相同则返回
        moveA=moveA->next;
        moveB=moveB->next;
    }
    return NULL;

九、判断链表中是否有环

题目链接:OJ链接
数据结构——单链表OJ题,数据结构,数据结构,链表
数据结构——单链表OJ题,数据结构,数据结构,链表

提示:

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

思路解析:
数据结构——单链表OJ题,数据结构,数据结构,链表

代码演示:

bool hasCycle(struct ListNode *head) {
    struct ListNode*move1=head;
    struct ListNode*move2=head;
    while(move1&&move2&&move2->next){//此处move2和move2->next的顺序不可交换
        move1=move1->next;           //否则会导致空指针错误
        move2=move2->next->next;
        if(move1==move2)
            return true;
    }
    return false;
}

总结

这九道单链表OJ都是我见过的很经典的题型!
在这里为大家分享一下!
希望有更多的人能够通过这些题目更好地掌握单链表相关的知识!文章来源地址https://www.toymoban.com/news/detail-626244.html

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

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

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

相关文章

  • 数据结构——单链表OJ题

    在前面的博客中我们知道了什么是单链表以及如何建立单链表! 现在让我们来检验一下学习成果吧! 提示:此博客中题目均来自牛客网以及力扣网!在题目中我会附带两大网站的链接,大家也可以去练习一下! 若有链接问题可以在评论区及时反馈! 题目链接: OJ链接 提示

    2024年02月14日
    浏览(82)
  • 【数据结构】单链表OJ题(一)

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️ 感谢大家点赞👍收藏⭐评论✍️ 目录 一、移除链表元素 💡方法一: 💡方法二: 二、链表的中间节点 💡方法一: 三、链表中倒数第k个结点 💡方法一: 四、反转链表 💡方法一:

    2024年02月13日
    浏览(80)
  • 【数据结构】单链表OJ题(二)

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、链表分割 💡方法一: 二、链表的回文 💡方法一:  三、相交链表 💡方法一:  四、环形链表  💡方法一:  🗒️前言: 在上一期中我们

    2024年02月14日
    浏览(40)
  • 数据结构——单链表OJ题(第二弹)

    此次练习题有两道! 有点小难度,但相信难不住大家的! 我也会给出两道OJ题的链接,大家也赶快去试一试吧 题目链接: OJ链接 提示: 链表中节点的数目范围在范围 [0, 104] 内 -105 = Node.val = 105 pos 的值为 -1 或者链表中的一个有效索引 本题有两个解析思路~ 代码演示: 提示:

    2024年02月14日
    浏览(40)
  • 【数据结构练习】单链表OJ题(二)

    题目: 示例: 注意:不能根据节点的值来比较是否相交,而是根据节点在内存中是否指向相同的位置。 例如以上图: 链表A:4、1、8、4、5 链表B:5、6、1、8、4、5 链表A和链表B都有节点的值为1,但是它们在内存中指向不同的位置,而值为8的节点(A的第三个节点、B的第四个

    2024年02月11日
    浏览(39)
  • 【数据结构练习】单链表OJ题(一)

    题目: 思路1: 在原来的链表上进行修改,节点的数据是val的删除,然后前后再连接起来。 需要考虑的因素: 1.要删除的节点位置在第一个节点; 2.要删除的节点位置在中间任意一个节点; 3.要删除的节点位置在最后一个节点 用一个变量cur遍历链表,要删除的节点是头节点

    2024年02月11日
    浏览(60)
  • 【LeetCode】【数据结构】单链表OJ常见题型(二)

     👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言: 【LeetCode】面试题02.04. 分割链表 【LeetCode】160. 相交链表 【LeetCode】141. 环形链表 【LeetCode】142. 环形链表Ⅱ 方法

    2024年02月14日
    浏览(45)
  • 【LeetCode】【数据结构】单链表OJ常见题型(一)

     👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》 🌝 每一个不曾起舞的日子,都是对生命的辜负。 目录 前言: 【LeetCode】203.移除链表元素 【LeetCode】206.反转链表  思路一 思路二 【LeetCode】876.链表的中间结点 快慢指针法

    2024年02月14日
    浏览(37)
  • 数据结构-链表-单链表(3)

    目录 1. 顺序表的缺陷 2. 单链表 2.1 单链表的基本结构与接口函数 2.2 重要接口 创建新节点的函数: 2.2.1 尾插 2.2.2 头插 2.2.3 尾删 2.2.4 头删 2.2.5 查找 2.2.6 插入 2.2.7 删除 2.2.8 从pos后面插入 2.2.9 从pos后面删除 3. 链表的缺陷与优势: 4. 链表与顺序表比较 写在最后: 为什么

    2024年01月17日
    浏览(109)
  • 数据结构——链表OJ题

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

    2024年02月21日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包