当前位置: 首页 > news >正文

建设工程交易网站代写新闻稿

建设工程交易网站,代写新闻稿,做电商的网站,贵阳网站建设网站制作​ ​📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(五)1. 合并…

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 链表OJ题(五)
    • 1. 合并两个有序链表
      • 1.1 思路--带哨兵位的头结点
      • 1.2 思路--不强行加头结点
  • 2.总结:

上一篇链表OJ题链接:【链表OJ题(四)】反转链表

链表OJ题(五)

1. 合并两个有序链表

链接:21. 合并两个有序链表

描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

示例1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例2:
输入:l1 = [], l2 = []
输出:[]
示例3:
输入:l1 = [], l2 = [0]
输出:[0]

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

1.1 思路–带哨兵位的头结点

之前做过一道题目,叫做合并两个有序数组。其中有一种方法是创建一个新数组,然后遍历两个数组,将两个数组的较小的元素放置到新数组中。一个数组遍历完,将没有放置的元素放置到新数组中,然后拷贝回原数组。

那么这道题能否借鉴它的思路?
合并两个有序链表,链表和数组不同,数组形式的一种方法需要我们创建一个新数组。但是对于链表而言我们可以通过指针改变链接关系,所以不需要创建新链表,只需要修改即可。
有序数组的做法是将较小元素逐个尾插到新数组中,那么我们也可以将较小元素尾插到链表中

那么链表为空如何处理?
这时就又要用到哨兵位(头结点)了,我们给一个哨兵位 head,它也不存储数据,那么不就可以了?但是注意有效数据从 head->next 开始。
在这里插入图片描述

但是尾插存在两个问题,当尾插的时候,我们需要找链表的尾,而且当链表为空时,需要特殊处理。为了避免每次找链表的尾,那么我们就给定一个 tail,这样只要将 tail 迭代就可以。
在这里插入图片描述

注意:哨兵位需要释放,否则会造成内存泄漏。
在这里插入图片描述

代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head = NULL, *tail = NULL;if (list1 == NULL){return list2;} if (list2 == NULL){return list1;}// 哨兵位// 这里 tail 也需要动态开辟一下// 因为不在迭代时进行第一次插入的处理// tail 一开始为空指针,会报错head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));   while (list1 && list2){if (list1->val < list2->val){tail->next = list1; // 当前结点链表的尾链接到 list1tail = list1; // 链表的尾变成 list1list1 = list1->next; // list1 并没有改变,list1 迭代到list1的下一个节点}else{tail->next = list2;tail = list2;list2 = list2->next;}}// 未放置完的元素// 这里和数组的完全不一样// 链表是串联的,所以只需要把当前节点给到tail->next// 就可以全部串联if (list1){tail->next = list1;}if (list2){tail->next = list2;}// 释放哨兵位struct ListNode* ans = head->next;free(head); return ans;
}

在这里插入图片描述

1.2 思路–不强行加头结点

这道题目不使用哨兵位也能写,但是使用这种方法时,需要处理一下链表第一次合并时尾插的情况,大体思路和带哨兵位差不多,但需要注意一下细节

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode *head, *tail;head = tail = NULL;while (list1 && list2){if (list1->val < list2->val){// 第一次合并if (tail == NULL){head = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{// 第一次合并if (tail == 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;
}

在这里插入图片描述

2.总结:

今天我们通过两种思路分析并完成合并两个有序链表这道链表OJ题目,也更加深层次了解和使用了带哨兵位的头结点这个思路,在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

在这里插入图片描述

http://www.zhongyajixie.com/news/8372.html

相关文章:

  • 哪里网站用vue.js做的网站结构优化的内容和方法
  • 丹凤县人民政府门户网站建设广州专业seo公司
  • 富阳网站建设怎样雷神代刷推广网站
  • wordpress改网址导航seo顾问服
  • 广州做网站(信科网络)百度免费下载安装
  • 学网页设计培训班seo sem推广
  • 律师网站建设网络舆情分析
  • 做网络课程的网站seo怎么发布外链
  • 做logo设计的网站快手刷粉网站推广
  • 建设网站要服务器seo交流
  • 汕头网站关键词优化教程白度指数
  • 如何做网站卖东西网络推广是指什么
  • wordpress破解教程黑帽seo培训
  • 西安做网站好的公司临沂头条新闻今日头条
  • 成都网站品牌设计网站搜索引擎优化工具
  • 如何建立自己的免费网站怎么打开网站
  • 深圳外包网站营销活动策划方案
  • 渝北集团网站建设免费推广论坛
  • 描述建设网站的一个具体步骤南京最新消息今天
  • 做美食分享网站源码今日油价92汽油
  • 丰镇网络推广厦门seo怎么做
  • 网站可以做10000件事情吗我们seo
  • 建设银行 上海科技中心网站会计培训班的费用是多少
  • 国外做机械设计任务的网站b2b免费外链发布
  • 牡丹江地区做网站的公司seo优化包括什么
  • 建设银行手机银行下载官方网站下载产品软文是什么
  • django网站开发教程中国搜索引擎份额排行
  • 企业网站建设运营的灵魂是什么seo还有未来吗
  • 手机网站建设的重要性已备案域名交易平台
  • 深圳网站建设 套餐网络营销一般月薪多少