首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

【LeetCode热题100】【链表】排序链表

排序链表 - 力扣(LeetCode) 要排序一个链表,最快方法用一个数组将链表节点值存起来然后排序数组后重新构建链表 但是面试角度,我们应该在链表原地排序,这里使用最简单归并排序 归并排序分三步...:如果其中一个链表为空,返回另一个链表,比较两个链表首节点大小,让小节点成为新链表头节点,递归合并后面的 ListNode *merge(ListNode *l1, ListNode *...l2) { if (l1 == nullptr)return l2; if (l2 == nullptr)return l1; if (l1->val next); return l2; } 最后归并排序链表,先找出链表中间位置拆分成两个链表,递归归并排序两个链表后合并 ListNode...(l1->val val) { l1->next = merge(l1->next, l2); return l1; }

6310

漫谈递归-链表合并

第一个题目 合并两个有序链表 认真阅读题目 将两个有序链表合并为一个新有序链表并返回。新链表通过拼接给定两个链表所有节点组成。...示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 线索 递归实现 新链表 有将两个有序链表合并成 假设有方法mergeTwoLists能实现这样功能。...步骤 1.如果一个链表(最简单开始) 就不需要合并 这就是结果 如果多个 采用归并排序。对象就是n个链表。 ?...示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 分析 链表无法通过下标直接定位 听过其他方法都不很合适 采用归并排序,数组通过下标来分段处理, 链表如何分段?...1 循环遍历 比较当前元素下个元素 如果相同 删除当前元素(删除下一个元素会有问题) 继续遍历 最坏情况 全部相同 [1,1,1,1,1,1,1] code struct ListNode* deleteDuplicates

61120
您找到你想要的搜索结果了吗?
是的
没有找到

Ural 1519 Formula 1 插头DP进阶

【输入】 本题就一组数据, 第一行nm, 2 ≤ N, M ≤ 12, 然后n*m字符矩阵, *表示障碍物. . 表示空白. 【输出】 回路个数....但是我会将写好程序网上神犇代码对拍, 发现没有问题,至少说明思路没有问题. 然后再改进空间复杂度. 既然dp含义初始值、以及我们目标值都已经知道了. 我们就来思考状态转移事情....如果令pq分别是j-1段j段轮廓线比特位情况(即p、q分别是L1左段、上段轮廓线)分别为pq的话, 【1】中其实是根据p=0,q=0、p=0,q=1、p=1,q=0、p=1,q=1 四种情况分情况讨论...因此 L2=L1-(1<<jz[j])+(1<<jz[j-1]) dp[i][j][L2]+=dp[i][j-1][L1] 注意, 上面轮廓线继续向下开拓(即从CD进入, 然后AB穿出)....如果轮廓线CD进入,然后BC穿出的话, 就像下图一样 ?

57410

LeetCode 刷题笔记——day 1

两数之和 难度:简单 给定一个整数数组 nums 一个整数目标值 target,请你在该数组中找出 为目标值 target 两个 整数,并返回它们数组下标。...两数相加 难度:中等 给你两个 非空 链表,表示两个非负整数。它们每位数字都是按照 逆序 方式存储,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示链表。...示例 2: 输入:l1 = [0], l2 = [0] 输出:[0] 示例 3: 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1]...思路 创建两个空指针,一个指向头部,一个跟随程序指向尾部,利用三目运算符提取目标数字且在其一链表提前截止时以 0 赋值(必须加入 if 语句判断,切忌指针继续后移),将得到数据处理后直接利用已有构造函数创建节点...) { l1 = l1->next; } if(l2) { l2 = l2->next;

27040

数据结构与算法 -4、5 :两数相加&&两数之和

其中,它们各自位数按照 逆序 方式存储,并且它们每个节点只能存储一位数字。如果,我们将这两个数相加起来,则会返回一个新链表来表示它们。...无非注意一点就是: 本题对链表操作,即将两个链表对应节点数据加存入另一个链表对应节点 注意链表对应数据相加时进位 以下给出C++JavaScript两种解法,但是思路都一样,所以请读者自行选择适合自己语言...) l1 = l1->next; if (l2) l2 = l2->next; } if (carry) cur->next = new...首先说第一个角度,数组层面来考虑,既然要从数组中找两个满足要求元素,那问题就可以抽象成数组中查找满足要求元素问题了,那解决方法不就出来了,无非就是查找方法事了呗,那笨一点,使用暴力解法,...),如果满足数组两个元素相加之和等于target值,除了arr[1]之外元素肯定存在一个数组元素值为target-arr[1],换种说法就是target-arr[i] ,i!

70710

面试题 02.05. 链表求和

链表求和 难度中等140 给定两个用链表表示整数,每个节点包含一个数位。 这些数位反向存放,也就是个位排在链表首部。 编写函数对这两个整数求和,并用链表形式返回结果。...示例: 输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295 输出:2 -> 1 -> 9,即912 **进阶:**思考一下,假设这些数位正向存放,又该如何解决呢?...示例: 输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295 输出:9 -> 1 -> 2,即912 ---- 思路: 这道题与数组求和以及字符串求和类似,都是用每一位相加还有加上进位求得结果赋给一个新链表...但记得最后判断是否还有多一个进位需要加上。 题目中还提到如果正向存放的话,那可以先用将两个链表值放到两个栈中,然后就像原来思路一样,只不过变成了栈中取数值而已!..., ListNode* l2) { //创建一个头节点 ListNode* newhead = new ListNode(-1); //创建一个新链表用于存储每个位

14820

合并两个有序链表

在循环体中,比较 l1->val l2->val 大小,如果 l1 值小于 l2,则将 l1 添加到合并后链表末尾,并将 l1 指针移动到下一个节点;否则,将 l2 添加到合并后链表末尾,并将...由于 dummy 一个临时节点,实际合并后链表 dummy.next 开始。 总体来说,这段代码通过迭代遍历两个升序链表,根据节点值大小将节点逐个合并,并返回合并后链表头节点指针。...我将为你介绍递归法解题思路代码示例。 递归法思路基于合并两个升序链表问题。...假设我们已经知道如何合并两个l1 l2 为头节点升序链表,我们可以将问题转化为合并以 l1->next l2 为头节点升序链表,并将结果连接到 l1 上。...然后,我们比较 l1->val l2->val 大小,如果 l1 值小于 l2,则将 l1 下一个节点与合并后链表连接,并返回 l1;否则,将 l2 下一个节点与合并后链表连接,并返回

9310

合并两个有序链表

合并两个有序链表,使得合并后结果仍然有序,直观做法就是两个链表首节点开始比较,将其中小那个链接到新链表之中,(如果不想破坏原链表,那么需要将该节点拷贝一份,然后链接到新链表之中。)..., List L2); //合并链表 int main() { List L1, L2, L; //构造L1L2链表 L1 = Read(); L2 = Read(); //合并L1L2...这个双指针用法还是很多。 ————————————————————9.16更新,并不华丽分割线—————————————————— 下面链表相对于数组一些特点。...求链表长度需要遍历整个链表,而不像数组一样只需要返回last+1。 插入删除操作如果出现在首节点处,将会迫使我们更改链表头指针。...线性表最基本数据结构,将来树图都将依赖于线性表来实现。(广义表结构)

5.1K20

链表有序,如何快速合并呢?

前言 大家好,我来自于华为程序员小熊。今天给大家带来一道链表相关题目,这道题同时也是字节、腾讯、亚马逊微软等大厂面试题,即力扣上第21题-合并两个有序链表。...本文主要介绍递归迭代两种策略来解答此题,供大家参考,希望对大家有所帮助。 合并两个有序链表 将两个升序链表合并为一个新升序链表并返回。 新链表通过拼接给定两个链表所有节点组成。 ?...l2 : l1; } /* 其中一个链表头节点值小于另一个,选值较小者作为新链表头节点 */ if(l1->val val) {.../* 将该链表剩余部分(链表)跟另一个合并 */ l1->next = mergeTwoLists(l1->next,l2); return l1; } else...l2 } } 复杂度分析 时间复杂度:O(n + m),其中 n m 分别为两个链表长度,需要递归调用两个链表每个节点一次。

57710

02-线性结构1 两个有序链表序列合并

Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */ L1L2给定带头结点单链表...,其结点存储数据递增有序;函数Merge要将L1L2合并为一个非递减整数序列。...(L1, L2); Print(L); Print(L1); Print(L2); return 0; } /* 你代码将被嵌在这里 */ 输入样例: 3 1 3 5 5 2 4 6 8 10 输出样例...: 1 2 3 4 5 6 8 10 NULL NULL ---- 思路很明确了,考虑到最后三种情况,值得思考我们需要声明一个结点指向L1,L2 ,因为,我们只能一个一个去传值,但又不能破坏L1,2L...先空 while(l1&&l2){//两个都不空时就接入 if(l1->DataData) { L->Next=l1; l1=l1->Next;//磨L1下一个结点

21710

题目----力扣--合并两个有序链表

题目 将两个升序链表合并为一个新 升序 链表并返回。新链表通过拼接给定两个链表所有节点组成。 ...示例 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 均按 非递减顺序 排列 解法 这里我们使用迭代方式将两个有序链表合并成一个有序链表...首先判断两个输入链表是否为空,如果有一个为空直接返回另一个链表。然后定义两个指针l1l2分别指向两个链表头部,再定义一个新链表头指针newHead尾指针newTail。...ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { // 判断list1或者list2是否为空表,如果直接返回另一个表即可

11610

Leetcode链表题目总结

如果题目要求「在两个中间结点时候,返回第一个中间结点」,此时快指针可以前进条件:当前快指针下一个结点当前快指针下下一个结点都非空。注意体会以上二者不同之处。...换句话说,如果一个链表第k个节点与另一个链表第j个节点同一节点(引用完全相同),两个链表相交。...解题思路   根据题意,两个链表相交指: 两个指针指向内容相同,说明该结点记在A链表上又在B链表上,进而说明AB相交 而对于相交情况,两条链表一定是这种结构: ?   ...如果该链表环形链表,那么当两个指针指向同一个节点时,该节点与目标节点距离(正向)head节点与目标节点距离相等。   ...假设有两个指针,分别为快慢指针fastslow, 快指针每次走两步,慢指针每次前进一步,如果有环两个指针必定相遇; A:链表起点 B:环起点 C:相遇点 X:环起点到相遇点距离 Y:链表起点到环起点距离

54120

【Leetcode -141.环形链表 -2.两数相加】

我们思路快慢指针,定义两个指针fastslow,fast每次走两步,slow每次走一步,如果有环的话,fast一定能追上slow;如图: fast走两步,slow走一步: fast走两步,...它们每位数字都是按照 逆序 方式存储,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。...示例 2: 输入:l1 = [0], l2 = [0] 输出:[0] 示例 3: 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1...while (l1 || l2) { //判断l1或者l2是否为空,为空返回0,不为空返回它val n1 = l1 ?...,即判断sum是否大于等于10 flag = sum / 10; //如果l1不为空,l1继续迭代 if (l1) { l1 = l1->next;

7410

反转链表、链表中间结点、合并两个有序链表【LeetCode刷题日志】

力扣(LeetCode)官网 - 全球极客挚爱技术成长平台 思路一:翻转单链表指针方向 这里解释一下三个指针作用: n1:记录上一个节点,如果第一个就指向空 n2:记录此节点位置 n3:记录下一个节点位置...如果两个中间结点,返回第二个中间结点。 力扣(LeetCode)官网 - 全球极客挚爱技术成长平台 思路一:单指针法 时间复杂度:O(N*1.5),其中 N 给定链表结点数目。...新链表通过拼接给定两个链表所有节点组成。..., struct ListNode* l2){ /*if判断: 1.如果l1为空,返回l2 2.如果l2为空,返回l1 3.如果l1值小于l2,比较l1next值l2...,并把值赋给l1下一个;返回l1 4.反之,比较l1l2next值,并把值赋给l2下一个;返回l2 */ if (l1 == NULL) { return

8710
领券