合并两个有序链表
[!Tip]
本节源代码见Github链接🔗
问题描述
如何将两个有序链表合并为一个新的有序链表
核心思路
通过递归迭代,比较两个链表元素结点的大小,然后依次合并。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 合并两个有序链表
*
* @param headNode1 链表1
* @param headNode2 链表2
* @return NormalListNode 新的链表表头指针
* @author: Max Solider
* @date: 2022/10/9 14:18
*/
NormalListNode mergeList(NormalListNode headNode1, NormalListNode headNode2) {
if (headNode1 == null) {
return headNode2;
}
if (headNode2 == null) {
return headNode1;
}
NormalListNode result = null;
if (headNode1.getData()
时间复杂度
时间复杂度为O(n),用于遍历链表。
空间复杂度
空间复杂度为O(n),用于栈空间。