经典链表试题(一)

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

经典链表试题(一),经典算法试题,链表,数据结构

📘北尘_:个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上,不忘来时的初心

一、两数相加

1、题目介绍

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
经典链表试题(一),经典算法试题,链表,数据结构


2、思路讲解

由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。具体而言,如果当前两个链表处相应位置的数字为 n1,n2,进位值为 carry,则它们的和为 n1+n2+carry;其中,答案链表处相应位置的数字为 (n1+n2+carry) mod 10,而新的进位值为 (n1+n2+carry)/10。
如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个 000 。
此外,如果链表遍历结束后,有 carry,还需要在答案链表的后面附加一个节点,节点的值为 carry。


3、代码实现

经典链表试题(一),经典算法试题,链表,数据结构


二、合并两个有序链表

1、题目介绍

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
经典链表试题(一),经典算法试题,链表,数据结构


2、思路讲解

先判断两个链表是否都为空,然后在创建一个新的链表,将旧链表的大小比较,一一放入新链表中。


3、代码实现

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* head=NULL,*tail=NULL;
    while(list1 && list2)
    {
        if(list1->val<list2->val)
        {
            if(head==NULL)
            {
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
            if(head==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }  
    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    return head;
    
}

三、环形链表(二)

1、题目介绍

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。
注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
经典链表试题(一),经典算法试题,链表,数据结构


2、思路讲解

我们定义两个指针,一个slow一个fast,slow一下走一步,fast一下走两步,如果该链表存在环,slow指针和fast指针一定会相遇
设环外链表长度为a,slow进入环后,又走了b步的距离与fast相遇,此时,设fast走完了n环,c为两指针相遇后环长减去b
fast为a+n(b+c)+b=a+(n+1)b+nc,slow=a+b,又因为fast=2slow,所以a=(n-1)b+n*c,从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。


3、代码实现

经典链表试题(一),经典算法试题,链表,数据结构


四、环形链表(一)

1、题目介绍

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。
经典链表试题(一),经典算法试题,链表,数据结构


2、思路讲解

设快慢指针,慢指针一下走一步,快指针一下走二步,如果两指针相遇,则存在环。


3、代码实现

经典链表试题(一),经典算法试题,链表,数据结构


五、删除链表中的结点

1、题目介绍

有一个单链表的 head,我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的,并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意,删除节点并不是指从内存中删除它。这里的意思是:

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。
自定义测试:

对于输入,你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点,而应该是链表中的一个实际节点。
我们将构建链表,并将节点传递给你的函数。
输出将是调用你函数后的整个链表。
经典链表试题(一),经典算法试题,链表,数据结构


2、思路讲解

思路一:讲node结点的后面的结点的值拷贝给node,并将node的下一个结点指向node的next的next
思路二:定义一个cur指针,指向node,并将node指向下一个结点,然后拷贝给cur


3、代码实现

思路一

经典链表试题(一),经典算法试题,链表,数据结构

思路二

经典链表试题(一),经典算法试题,链表,数据结构


六、环形链表中的约瑟夫问题

1、题目介绍

经典链表试题(一),经典算法试题,链表,数据结构


2、思路讲解

先创建一个链表,然后一一赋值,定义一个cur指针指向头结点,如果到了m的时候,prev指向cur的后结点并且释放掉cur,并且cur指向prev的next,如果不到m,讲prev指向cur,cur在指向cur的next,循环终止的条件是,cur的下一个结点就是cur,代表只有最后一个人了。文章来源地址https://www.toymoban.com/news/detail-720160.html


3、代码实现

typedef struct ListNode ListNode;

ListNode* BuyNode(int i)
{
    ListNode* newnode=malloc(sizeof(ListNode));
    if(newnode==NULL)
    {
        exit(-1);
    }
    newnode->next=NULL;
    newnode->val=i;
    return newnode;
}
ListNode* Create(int n)
{
    ListNode* head,*tail;
    int i=1;
    head=tail=BuyNode(i++);
    while(i<=n)
    {
        tail->next=BuyNode(i++);
        tail=tail->next;

    }
    tail->next=head;
    return head;

}
int ysf(int n, int m ) {
   
    ListNode* head=Create(n);
    ListNode* prev=NULL;
    ListNode* cur=head;
    int i=1;
    while(cur!=cur->next)
    {
        if(i==m)
        {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
            i=1;
        }
        else 
        {

            prev=cur;
            cur=cur->next;
            i++;
        }
    }
    return cur->val;
}

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

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

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

相关文章

  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(65)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(83)
  • 【数据结构与算法】之多指针算法经典问题

    本文为 【数据结构与算法】多指针算法经典问题 相关介绍,下边将对 链表反转 (包含 迭代反转链表 、 递归反转 、 头插法反转 ), 双指针-快慢指针 (包含 寻找单向无环链表的中点 、 判断单向链表是否有环及找环入口 ), 双指针-左右指针 (包含 两数之和 、 二分查

    2024年02月03日
    浏览(68)
  • 【数据结构与算法】链表

    对于顺序表存在一些缺陷: 中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插

    2023年04月09日
    浏览(48)
  • 【算法与数据结构】链表

    链表是由一串节点串联在一起的,链表的每个节点存储两个信息:数据+下一个节点的地址 分清楚两个概念:什么是内存内部,什么是程序内部 内存内部: 信息存储在内存空间里的 程序内部: 通过什么信息,去操作结构 如果想操作链表的话,我们依靠的是程序内部的信息,

    2024年02月03日
    浏览(45)
  • 02-链表 (数据结构和算法)

    3.1 链表的基本概念 前面我们在学习顺序表时,线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在物理位置上也是相邻的。我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。为

    2024年02月16日
    浏览(46)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(59)
  • 【数据结构与算法】双向链表

    作者:旧梦拾遗186 专栏:数据结构成长日记   带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。 现在我们来通

    2024年02月11日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包