数据结构--单链表OJ题

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

上文回顾---单链表

这章将来做一些链表的相关题目


目录

1.移除链表元素

2.反转链表

3.链表的中间结点

4.链表中的倒数第k个结点

5.合并两个有序链表

6.链表分割

7.链表的回文结构

8.相交链表

9.环形链表

​编辑 

10.环形链表II

​编辑 ​编辑


1.移除链表元素

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

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

 思路:我们可以通过循环链表,判断结点的val与给出的val是否一致,一致则跳过该结点即可

由于我们是跳过某个结点,那么就会让这个结点的上一个结点和下一个结点进行关联;所以我们以某结点的next的val去判断;所以对于头结点来说,我们还要创建一个结点连接着头结点;

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

我们自己创建一个结点,还可以规避头指针为空的问题; 

答案:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


 struct ListNode* removeElements(struct ListNode* head, int val){
  //哨兵位
  struct ListNode* newhead=malloc(sizeof(struct ListNode));
  newhead->next=head;
  struct ListNode* cur=newhead;
  
  
  while(cur->next)
  {
      //判断下一个的值
     if(cur->next->val==val)
     {
         cur->next=cur->next->next;
     }
    else{
         cur=cur->next;
     }
      
  }
  //返回头指针
  return newhead->next;

}

2.反转链表

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

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

 思路:这道题实际上就是让结点的next改变即可;

所以在这里,我们创建3个指针prev,cur,next,让cur的next指向prev,然后进行指针移动,循环往复;一开始的prev指向NULL;如果head为空,那么就特殊处理,直接返回空;

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

 

答案:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    //特殊条件
   if(head==NULL)
   {
       return NULL;
   }
   struct ListNode* cur=head;
   struct ListNode* prev=NULL;
   struct ListNode* next=head->next;
   //移动指针
   while(cur)
   {
       cur->next=prev;
       prev=cur;
       cur=next;
       //判断next
       if(next!=NULL)
       {
            next=next->next;
       }
      
   }
   return prev;
}

3.链表的中间结点

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

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

 思路1:我们可以先算出链表的总长度,然后再取中间结点的位置

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    //先确定链表长度
    int i=0;
    struct ListNode* node=head;
    while(node!=NULL)
    {
        node=node->next;
        i++;
    }
    //确定中间节点位置
    int k=i/2;
    for(int i=0;i<k;i++)
    {
        head=head->next;
    }
    return head;
}

思路2:利用快慢指针的思想

我们只有在链表遍历到为NULL才知道结束,那么我们是否可以利用当指针到达末尾时就知道中间位置的思想呢?

这里我们用到的快慢指针思想就可以解决该问题,利用它们的速度差,走到的长度就是不一样的;

快指针一次跨越2个结点,而慢指针一次跨越1个结点,等到快指针到达末尾时,慢指针刚好到达中间位置

对于两个中间结点的,我们需要让快指针走到NULL才能达到第二个结点;而一个中间结点的,只需要让快指针走到最后一个结点即可

答案:

struct ListNode* middleNode(struct ListNode* head){
    //快慢指针
    struct ListNode* slow,*fast;
    slow=fast=head;
    //移动
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

 


4.链表中的倒数第k个结点

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

思路:这里还是利用到快慢指针的思想;还是利用快指针到达末尾,然后得知结点的思路;

只不过这里利用的是快慢之间的相对距离,上一题是快慢之间的相对速度;

我们可以让fast指针先走k步,然后在让slow和fast同时走,那么当fast指针到达NULL时, slow刚好到达返回的结点;

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

 这里要注意的几个特殊情况:头指针为空;k的大小超过链表长度

答案:

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    if(pListHead==NULL)
    {
        return NULL;
    }
    //利用相对距离
    struct ListNode* slow,*fast;
    slow=fast=pListHead;
    //先走k步
    while(k&&fast)
    {
        fast=fast->next;
        k--;
    }
    if(k>0)
    {
        return NULL;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;

}

 


5.合并两个有序链表

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

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

 思路:这里我们先创建一个结点,通过判断两链表的头结点的val大小,来决定连接着哪个

然后循环遍历,移动指针,执行同样的操作;

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

 当某一链表结束了,需要链接另一条链表剩余的结点;

答案:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //哨兵位
   struct ListNode* prehead=malloc(sizeof(struct ListNode));
   //比大小
   struct ListNode* prev=prehead;
   while(list1&&list2)
   {
       if(list1->val<list2->val)
       {
           prev->next=list1;
           list1=list1->next;
           prev=prev->next;
       }
       else
       {
           prev->next=list2;
           list2=list2->next;
           prev=prev->next;
       }
   }
   //判断哪个链表有剩余
   prev->next=list1==NULL?list2:list1;
   return prehead->next;
}

 


6.链表分割

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

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

 思路:我们可以创建2个结点,第一个结点连接着比x小的结点,第二个连接着>=x的结点

最后将着两个新链表连接在一起;

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

这里要注意,最后的结点要接空,否则该结点的next保持不变,可能会造成环,将会报错;

 

答案:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* prevHead1=(struct ListNode*)malloc(sizeof(ListNode));
        struct ListNode* prevHead2=(struct ListNode*)malloc(sizeof(ListNode));
         
        ListNode* tail1=prevHead1;
        ListNode* tail2=prevHead2;

        while(pHead)
        {
            if(pHead->val<x)
            {
                tail1->next=pHead;
                tail1=tail1->next;
            }
            else {
             tail2->next=pHead;
                tail2=tail2->next;
            }
            pHead=pHead->next;
        }

        //连接
        tail1->next=prevHead2->next;
        //尾置空
        tail2->next=NULL;

        return prevHead1->next;

    }
};

 


7.链表的回文结构

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

思路:这里我们没有办法从后走向前,单链表是单向的;所以我们可以只能从前往后走;

我们可以先找到中间结点,然后对中间结点之后的链表进行倒转,最后通过中间指针和头指针遍历,判断对应的val是否相同即可

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

 

答案:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head){
        //快慢指针
        struct ListNode* slow,*fast;
        slow=fast=head;
        //移动
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }

    struct ListNode* reverseList(struct ListNode* head){
        //特殊条件
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* cur=head;
    struct ListNode* prev=NULL;
    struct ListNode* next=head->next;
    //移动指针
    while(cur)
    {
        cur->next=prev;
        prev=cur;
        cur=next;
        //判断next
        if(next!=NULL)
        {
                next=next->next;
        }
        
    }
    return prev;
    }


    bool chkPalindrome(ListNode* head) {
      ListNode* mid=middleNode(head); //找中间
      ListNode* rmid=reverseList(mid); //中间位置后面倒置
      //比较
      while(rmid)
      {
        if(head->val!=rmid->val)
        {
            return false;
        }
        head=head->next;
        rmid=rmid->next;

      }

        return true;
    }
};

 


8.相交链表

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

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

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

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

 

思路:我们要看作是两条链表,然后后半部分连接是相同部分的结点

发现相交的链表的相交部分都是一样的;我们可以利用它们的尾结点来判断是否相交

对于没有相交的部分,我们无法确保它们的长度;所以我们可以先让比较长的链表先走长度差,然后再一起访问;当访问的结点一致时,表明找到了相交的第一个结点;

答案:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int lenthA=1,lenthB=1;
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;

    //计算链表长度
    while(curA->next)
    {
        ++lenthA;
        curA=curA->next;
    }
    while(curB->next)
    {
        ++lenthB;
        curB=curB->next;
    }
    //尾节点判断,不一样说明没有香蕉
    if(curA!=curB)
    {
        return NULL;
    }
    //长度先走差距步
    struct ListNode* longList=headA,*shortList=headB;
    int abs=fabs(lenthA-lenthB);
   if(lenthA<lenthB)
   {
       longList=headB;
       shortList=headA;
   }
   while(abs--)
   {
       longList=longList->next;
   }
    //找到相同的交点
   while(longList!=shortList)
   {
       longList=longList->next;
       shortList=shortList->next;
   }

   return longList;
}

 这里要注意,curA,curB只能走到尾结点,目的是为了判断它们是否相同,是否相交;


9.环形链表

 

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

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

思路:还是利用快慢指针的思想;

假设有环,通过快慢指针, 快指针一定先进入环中,当慢指针进入环时,让快指针去追逐慢指针

如果快指针走到了空,表示没有环;

这里我们让快指针走两步,让慢指针走1步;当慢指针进入环时,假设快指针到慢指针距离为N,那么没走一次,它们之间的距离就会减1,直至减到N为0,表示快指针追到了

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

 

答案:

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
   //快慢指针
   //赛道追逐问题
   struct ListNode* slow=head;
   struct ListNode* fast=head;
   while(fast&&fast->next)
   {
    
       fast=fast->next->next;
       slow=slow->next;
       if(fast==slow)
       {
           return  true;
       }
       
   }
   return false;

}

这里为什么不让快指针走3步,让慢指针走1步呢?

假设慢指针进入循环后它们之间距离为N

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

每走一次,它们之间的距离就会减2,N-2,N-4……

如果N为偶数,那么减到最后可以为0,那么就表示追上了,

而如果N为奇数,那么追到最后为1或者-1,不是差一点追上,就是追过了,所以它们的相遇还要考虑环的周长,追过了距离就变为周长-1;

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

 

到最后,可能追上了,可能一直遇不到;

例如:

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

当slow在左边,fast就在右边;slow在右边,fast就在左边;永远都遇不到

所以为了方便解决问题,就让快指针走2步即可; 


10.环形链表II

 

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

思路:这里我们要在第9题的思想上再引入数学的思想;

假设起点到环入口距离为L,环周长为C,入口到相遇点距离X;

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

fast指针走的距离是slow指针的2倍,所以fast指针会先进入环中, fast可能会在环中绕几圈,我们设为n

那么slow指针走的距离为L+X;

fast指针走的距离为L+n(n>=1)*C+X,fast指针要追上slow,至少要绕一圈环

那么通过它们之间的关系

得到2(L+X)=L+n*C+X

最终得到L=(n-1)*C+C-X;

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

 也就是说,L的距离会等于n圈环的周长加上相遇点到入口的距离;

那么将得出结论:

一个指针从起点走,一个指针从相遇点走,它们将会在入口点相遇

 答案:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    //快慢指针
    struct ListNode* fast,*slow;
    fast=slow=head;
    //有环
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        //相遇点
        if(fast==slow)
        {
            struct ListNode* meet=fast;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

通过分析之后,我们不需要管那些未知数;

假设L很长,环很小,那么在相遇点的指针就会在环中多走几圈;

假设L很短,那么相遇点到入口点的距离就刚好是L的长度;

所以在写代码中,我们只需要知道起始的指针和相遇点的指针最终会相遇,且就是入口点。文章来源地址https://www.toymoban.com/news/detail-634404.html

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

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

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

相关文章

  • 【数据结构练习】单链表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)
  • 数据结构——单链表OJ题(第二弹)

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

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

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

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

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

    2024年02月14日
    浏览(42)
  • 【数据结构】移除链表元素-图文解析(单链表OJ题)

    LeetCode链接:203. 移除链表元素 - 力扣(LeetCode) 本文导航 💭做题思路 🎨画图更好理解: ✍️代码实现 🗂️分情况讨论: ❄️极端情况: 遍历链表,找到值为 val 的节点删除 这里需要两个指针  cur 用来遍历链表  prev 指向 cur 的前一个位置,方便删除一个节点后,链接前

    2024年02月14日
    浏览(33)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(68)
  • 数据结构:带环单链表基础OJ练习笔记(leetcode142. 环形链表 II)(leetcode三题大串烧)

    目录 一.前言  二.leetcode160. 相交链表  1.问题描述 2.问题分析与求解 三.leetcode141. 环形链表 1.问题描述 2.代码思路  3.证明分析  下一题会用到的重要小结论: 四.leetcode142. 环形链表 II 1.问题描述 2.问题分析与求解 Judgecycle接口: 方法一: 方法二:  单链表和带环单链表

    2023年04月08日
    浏览(37)
  • 【数据结构】数据结构小试牛刀之单链表

    不讲虚的啦,直接肝! 单链表所要实现的功能罗列如下: 初始化工作我们先初始化一个节点类型,类型中包括了数据域和指针域,数据与中保存着该节点要保存的数据,指针域则保存着链表下一个节点的地址: 然后我们在创建一个函数,用于创建一个新的节点,因为后面我

    2023年04月24日
    浏览(59)
  • 【数据结构】单链表详解

    当我们学完顺序表的时候,我们发现了好多问题如下: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们 再继续插入了

    2024年02月09日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包