算法题题解:合并两个有序链表(C语言和java实现)
LeetCode原题: 21. 合并两个有序链表
思路
1.先考虑特殊情况:有一条链为空链,则另一条链就是合并结果,直接return,后面的操作都不执行。
2.再考虑一般情况:两条链都不为空,则要进行合并。
解题过程
有空链情况:直接return另一条链。
无空链情况:
1.创建一个虚拟头节点list3,指针p用于更新list3的节点,初始是指向虚拟头节点list3;
2.循环比较两条链各个节点的值大小,比较出值小的链接到合并链的后面,直到出现一条链比较;
3.最后,将剩余的节点直接接到合并链的链尾,合并完成,合并链的第一个节点为虚拟节点list3的下一个节点。
复杂度
时间复杂度: O(n)
空间复杂度: O(1)
题解代码
C语言版
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 先考虑特殊情况:有空链
if(!list1 || !list2){
return (list1 == NULL) ? list2 : list1;
}
// 一般情况:都不为空,合并
struct ListNode list3; // 创建一个虚拟头节点
struct ListNode *p = &list3; // 创建一个指针,用于更新list3的节点
// 合并过程
while(list1 && list2){
if(list1->val <= list2->val){
p->next = list1;
list1 = list1->next;
}
else{
p->next = list2;
list2 = list2->next;
}
p = p->next;
}
// 将剩余的部分直接链接到后面
p->next = (list1 == NULL) ? list2 : list1;
return list3.next; // 虚拟头节点的下一个节点是合并后的第一个节点
}
java版
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 有空链
if(list1 == null || list2 ==null){
return (list1 == null) ? list2 : list1;
}
// 无空链
ListNode list3 = new ListNode(); // 初始化一个空的节点对象
ListNode p = list3; // 节点对象的引用p指向list3
// 合并过程
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
p.next = list1;
list1 = list1.next;
}
else{
p.next = list2;
list2 = list2.next;
}
p = p.next;
}
p.next = (list1 == null) ? list2 : list1;
return list3.next;
}
}
谢谢观看!如果觉得博客对您有用的话,还请帮我点点赞,加个关注,一起学习算法。
原文地址:https://blog.csdn.net/m0_74412436/article/details/142642130
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!