【数据结构初阶】链表OJ

链表OJ

    • 题目一:移除链表元素
    • 题目二:反转链表
    • 题目三:链表的中间节点
    • 题目四:链表中倒数第k个结点
    • 题目五:合并两个有序链表
    • 题目六:链表分割
    • 题目七:链表的回文结构
    • 题目八:相交链表
    • 题目九:环形链表
    • 题目十:环形链表II

题目一:移除链表元素

OJ
在这里插入图片描述
方案一:

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head, * prev = NULL;
    while (cur)
    {
        if (cur->val == val)
        {
            if (cur == head)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

方案二:

题目解析:把原链表遍历一遍,插入新链表
在这里插入图片描述

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* newnode = NULL, * tail = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val == val)
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
        else
        {
            if (tail == NULL)
            {
                newnode = tail = cur;
                //tail = tail->next;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
    }
    if (tail)
        tail->next = NULL;
    return newnode;
}

题目二:反转链表

OJ
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* newnode = NULL, * cur = head;
    while (cur)
    {
        struct ListNode* next = cur->next;
        //尾插
        cur->next = newnode;
        newnode = cur;
        cur = next;
    }
    return newnode;
}

题目三:链表的中间节点

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{
    int val;
    struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

题目四:链表中倒数第k个结点

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) 
{
    struct ListNode* fast = pListHead, * slow = pListHead;
    while (k--)
    {
        if (fast == NULL)
            return NULL;
        fast = fast->next;
    }
    while (fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

题目五:合并两个有序链表

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{
    int val;
    struct ListNode* next;
};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if (list1 == NULL)
        return list2;
    if (list2 = NULL)
        return list1;
    struct ListNode* tail = NULL, * head = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    if (list1)
        tail->next = list1;
    if (list2)
        tail->next = list2;
    struct ListNode* del = head;
    head = head->next;
    free(del);
    return head;
}

题目六:链表分割

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
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* lhead, * ltail, * gtail, * ghead;
        ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                ltail->next = cur;
                ltail = ltail->next;
            }
            else
            {
                gtail->next = cur;
                gtail = gtail->next;
            }
            cur = cur->next;
        }
        ltail->next = ghead->next;
        gtail->next = NULL;
        struct ListNode* head = lhead->next;
        free(lhead);
        free(ghead);
        return head;
    }
};

题目七:链表的回文结构

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* fast = head, * slow = head;
		while (fast && fast->next)
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		return slow;
	}
	struct ListNode* reverseList(struct ListNode* head)
	{
		struct ListNode* newnode = NULL, * cur = head;
		while (cur)
		{
			struct ListNode* next = cur->next;
			cur->next = newnode;
			newnode = cur;
			cur = next;
		}
		return newnode;
	}
	bool chkPalindrome(ListNode* A)
	{
		struct ListNode* mid = middleNode(A);
		struct ListNode* rmid = reverseList(mid);
		while (A && rmid)
		{
			if (A->val != rmid->val)
				return false;
			A = A->next;
			rmid = rmid->next;
		}
		return true;
	}
};

题目八:相交链表

OJ
在这里插入图片描述

题目解析:
定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交
在这里插入图片描述

代码演示:
struct ListNode
{

    int val;
    struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
    struct ListNode* curA = headA, * curB = headB;
    int lenA = 1, lenB = 1;
    while (curA)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB)
    {
        curB = curB->next;
        lenB++;
    }
    if (curA != curB)
        return false;
    int gab = abs(lenA - lenB);
    struct ListNode* longest = headA, * shortest = headB;
    if (lenA < lenB)
    {
        longest = headB;
        shortest = headA;
    }
    while (gab--)
    {
        longest = longest->next;
    }
    while (shortest != longest)
    {
        
        shortest = shortest->next;
        longest = longest->next;
    }
    return longest;
}

题目九:环形链表

OJ

在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode {
    int val;
    struct ListNode* next;
};
bool hasCycle(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    return false;
}

题目十:环形链表II

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{
    int val;
    struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            while(meet != head)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

💘不知不觉,【数据结构初阶】链表OJ以告一段落。通读全文的你肯定收获满满,让我们继续为数据结构学习共同奋进!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/150174.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JavaScript概述

一、JavaScript简介&#xff1a; JavaScript是互联网上流行的脚本语言&#xff0c;可用于HTML和web&#xff0c;可广泛应用于服务器、PC、笔记本、平板电脑和智能手机等设备。 JavaScript是一种轻量级的编程语言&#xff0c;可插入HTML页面的编程代码&#xff0c;插入HTML页面后…

联盟 | Quick Creator X HelpLook ,AI助力打造出海企业内容营销

随着人工智能的快速发展&#xff0c;各行各业也加快了人工智能工具的探索&#xff0c;积极将AI融入到行业发展中&#xff0c;出海外贸也不例外。AI渐渐地融入到外贸的各个环节&#xff0c;为企业出海提速增效。 为此&#xff0c;「 Quick Creator 」与 「 HelpLook 」达成战略合…

mask-rcnn原理与实战

一、Mask R-CNN是什么&#xff0c;可以做哪些任务&#xff1f; Mask R-CNN是一个实例分割&#xff08;Instance segmentation&#xff09;算法&#xff0c;可以用来做“目标检测”、“目标实例分割”、“目标关键点检测”。 1. 实例分割&#xff08;Instance segmentation&am…

Python爬虫的七个常用技巧总结,这些你一定得知道!

文章目录 前言1、基本抓取网页2、使用代理IP3、Cookies处理4、伪装成浏览器5、验证码的处理6、gzip压缩7、多线程并发抓取关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战…

前端element的el-tooltip鼠标经过显示文字,没有文字显示空黑框问题

场景&#xff1a; 有时候在使用element的el-tooltip时会使用三元表达式&#xff0c;满足某个条件后才显示提示文字&#xff0c;否则不展示文字&#xff0c;但是却出现在在没有文字时展示了黑框&#xff0c;如下图&#xff1a; 解决方案&#xff1a; 加一个disabled便可&#…

手机维修店服务预约小程序的效果怎样

手机维修店在每个城市的商业街或商场里都很常见&#xff0c;目前人手一个或多个手机&#xff0c;虽然手机质量有了提升&#xff0c;但各种毛病依然无法避免&#xff0c;因此手机维修店虽然不是人挤人&#xff0c;但整体生意还可以&#xff0c;各种服务也愈加完善。 而市场接受…

人力物力和时间资源有限?守住1个原则,精准覆盖所有兼容性测试!

随着 APP 应用范围越来越广&#xff0c;用户群体越来越大&#xff0c;终端设备的型号也越来越多&#xff0c;移动终端碎片化加剧&#xff0c;使得 APP 兼容性测试成为测试质量保障必须要考虑的环节。 APP 兼容性测试通常会考虑&#xff1a;操作系统、厂家 ROM、屏幕分辨率、网…

掌握Python中的控制流语句:break, continue, quit的应用技巧详解

引言 在Python编程中&#xff0c;控制流语句是非常重要的一部分&#xff0c;它们可以帮助我们控制程序的执行流程。其中&#xff0c;break、continue和quit是常用的控制流语句&#xff0c;它们可以在循环中起到关键作用。本文将详细介绍这些控制流语句的应用技巧&#xff0c;帮…

7天入门python系列之爬取热门小说项目实战,互联网的东西怎么算白嫖呢

第七天 Python项目实操 编者打算开一个python 初学主题的系列文章&#xff0c;用于指导想要学习python的同学。关于文章有任何疑问都可以私信作者。对于初学者想在7天内入门Python&#xff0c;这是一个紧凑的学习计划。但并不是不可完成的。 学到第7天说明你已经对python有了一…

Playwright UI 自动化测试实战

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…

VSCode配置MingW编译调试环境

1.MingW简介 MinGW&#xff0c;即 Minimalist GNU For Windows。它是一些头文件和端口库的集合&#xff0c;该集合允许人们在没有第三方动态链接库的情况下使用 GCC&#xff08;GNU Compiler C&#xff09;产生 Windows32 程序。 实际上 MinGW 并不是一个 C/C 编译器&#xf…

亚马逊产品召回后如何重新发布商品?儿童睡衣,婴儿沐浴座椅,不锈钢儿童水杯被召回

近日&#xff0c;又有一款亚马逊热销超34w的产品出现安全问题。据外媒报道&#xff0c;7月20日&#xff0c;CPSC发现一款产品名为CUPKIN双层不锈钢儿童水杯存在铅中毒的风险&#xff0c;该水杯的铅含量超过联邦铅含量禁令。 CPSC在召回公告中指出&#xff0c;因为铅极容易被6岁…

南湖HIT论坛|《医疗数据安全风险分析及防范实践(2023)》正式发布

11月11日&#xff0c;2023年南湖HIT论坛在浙江嘉兴隆重举行。作为颇受HIT从业者关注的年度盛会——本届论坛以“数据驱动医院运营管理”为主题&#xff0c;全国各地医疗机构信息主管和骨干围绕“数据驱动运营管理、运营数据中心建设、数据治理和数据安全”等话题展开深入研讨。…

Python自动化测试:web自动化测试——Selenium框架

web自动化测试1 Selenium介绍web自动化实现原理环境准备1&#xff09;Seleniumpython环境搭建安装步骤环境变量的配置 2&#xff09;浏览器驱动驱动下载驱动环境配置 3&#xff09;版本检查4&#xff09;其他异常情况排查版本不一致未激活卸载、降低/升级setuptools版本 web自动…

什么是CSV文件,以及如何打开CSV文件格式

​CSV代表Comma Separated Values。CSV文件是一种纯文本文件&#xff0c;用于存储表格和电子表格信息。内容通常是由文本、数字或日期组成的表格。使用将数据存储在表中的程序可以轻松导入和导出CSV文件。 CSV文件格式 通常CSV文件的第一行包含表格列标签。后面的每一行表示表…

【软考篇】中级软件设计师 第三部分(一)

中级软件设计师 第三部分&#xff08;一&#xff09; 十七. I/O管理软件十八. 输入/输出技术十九. 总线系统二十. 磁盘管理20.1 移臂调度算法20.2 缓冲区 二十一. 操作系统二十二. 数据库22.1 三级模式-两级映射22.2 数据库设计22.3 规范化理论22.4 范式判断22.5 模式分解 二十…

单链表按位查找 按值查找与 求表长

按位查找 #define NULL 0typedef struct LNode {int data;struct LNode *next; }LNode,*LinkList;//按位查找&#xff0c;返回第i个元素&#xff08;带头结点&#xff09; LNode* GetElem(LinkList L,int i){if(i<0)return NULL;LNode *p L;int j 0;while (p!NULL &&a…

使用 MATLAB HDL Coder 和 FPGA 快速实现自动白平衡(AWB)

使用 MATLAB HDL Coder 和 FPGA 快速实现自动白平衡&#xff08;AWB&#xff09; 在此项目中&#xff0c;我们将使用 MATLAB Simulink 和 HDL 编码器创建自定义 IP -- AWB。 MATLAB 设计 自动白平衡模块的设计是使用 HDL Coder 在 MATLAB 和 Simulink 中创建的。HDL Coder能够生…

免费开源客服机器人tiledesk 实现一个查询天气机器人

第一步,槽位收集: 第二步:天气api接口调用: 效果展示:

云原生下GIS服务规划与设计

作者&#xff1a;lisong 目录 背景云原生环境下GIS服务的相关概念GIS服务在云原生环境下的规划调度策略GIS服务在云原生环境下的调度手段GIS服务在云原生环境下的服务规划调度实践 背景 作为云原生GIS系统管理人员&#xff0c;在面对新建的云GIS系统时&#xff0c;通常需要应对…