算法题题解：合并两个有序链表（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;}
}