您现在的位置是:首页 > Javascript
当前栏目
聊一聊合并两个排序的链表
2023-02-25 18:02:32 时间
前言
给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序。本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文。
思路分析
经过前面的学习,我们知道了有关链表的操作可以用指针来完成。同样的,这个问题也可以用双指针的思路来实现:
- p1指针指向链表1的头节点
- p2指针指向链表2的头节点
声明一个变量存储合并后的链表,比对两个指针指向的节点值大小:
- 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点的值,p1指针继续向前走,进行下一轮的比对。
- 如果p2指针指向的节点值比p1指向的值小,合并后的链表节点就取p2节点的值,p2指针继续向前走,进行下一轮的比对。
- 当p1节点指向null时,合并后的链表节点就为p2所指向的链表节点;当p2节点指向null时,合并后的链表节点就为p1所指向的链表节点。
实现代码
看完上述分析后,聪明的开发者已经想到代码怎么写了。没错,这就是典型的递归思路,代码如下:
- 声明一个函数MergeLinkedList,它接受2个参数:递增排序的链表1,递增排序的链表2。
- 递归的基线条件:链表1为null就返回链表2,链表2为null就返回链表1。
- 声明一个变量pMergedHead用于存储合并后的链表头节点。
- 如果当前链表1的节点值小于链表2的节点值。
pMergedHead的值就为链表2的节点值。
pMergedHead的下一个节点值就为链表1的下一个节点和链表2的节点值比对后的值(递归)。
- 否则
pMergedHead的值就为链表1的节点值。
pMergedHead的下一个节点值就为链表2的下一个节点和链表1的节点值比对后的值(递归)。
- 最后,返回pMergedHead
export function MergeLinkedList(
firstListHead: ListNode | null,
secondListHead: ListNode | null
): ListNode | null {
// 基线条件
if (firstListHead == null) {
return secondListHead;
}
if (secondListHead == null) {
return firstListHead;
}
let pMergedHead: ListNode | null = null;
if (firstListHead.element < secondListHead.element) {
pMergedHead = firstListHead;
pMergedHead.next = MergeLinkedList(firstListHead.next, secondListHead);
} else {
pMergedHead = secondListHead;
pMergedHead.next = MergeLinkedList(firstListHead, secondListHead.next);
}
return pMergedHead;
}
测试用例
接下来,我们用思路分析章节中的例子来测试下我们的代码能否正常执行。
const firstLinkedList = new LinkedList();
firstLinkedList.push(1);
firstLinkedList.push(3);
firstLinkedList.push(5);
firstLinkedList.push(7);
firstLinkedList.push(9);
const secondLinkedList = new LinkedList();
secondLinkedList.push(2);
secondLinkedList.push(4);
secondLinkedList.push(6);
secondLinkedList.push(8);
const resultListHead = MergeLinkedList(
firstLinkedList.getHead(),
secondLinkedList.getHead()
);
console.log(resultListHead);
示例代码
本文所列举的代码,其完整版请移步:
- MergeLinkedList.ts
- MergeLinkedList-test.ts
相关文章
- JDK中内嵌JS引擎介绍及使用
- 49195,npm最后的疯狂?盘点10款最有前途JavaScript构建工具
- 译文:5个增强Node.js应用程序增强功能
- 4个例子,吃透 JavaScript 实现的二叉搜索树 BST
- Vue中使用XML和JSON格式互转插件
- JDK中Jshell简单使用(JDK9版本以上或者JDK9版本)
- shiro中的JSP标签支持
- Java技术点-json转对象,对象转json
- SpringBoot+SpringDataJpa @Query之 JPQL使用书写模板(模糊查询and条件查询)
- Spring Boot中的Freemarker模版引擎引用css和js的正确姿势
- Node.js解压版的环境配置及相关常用命令
- JSP学习笔记(6)—— 自定义MVC框架
- JSP学习笔记(5)——Servlet、监听器、过滤器、MVC模式介绍
- Jsp学习笔记(4)——分页查询
- APIJSON简单使用
- JSP学习笔记(3)——JSTL 标签库
- JSP学习笔记(1)——Jsp指令、动作元素和内置对象
- JavaScript ES6 Promise对象
- Web前端——JavaScript扩展补充
- Web前端——表单提交和Js添加选项