合并两个有序链表

LeetCode第二十一题

题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists

思路

因为节点插入操作要获得插入位置之前的那个节点，所以取第一个值更小的那个链表为母链表，将另外一个链表节点插入至母链表中即可。其中注意插入节点的写法和边界条件的处理。

源代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(!l1)
        return l2;
    if(!l2)
        return l1;
    struct ListNode * small;
    struct ListNode * large;
    struct ListNode * l;
    struct ListNode * head;
    struct ListNode * rear;
    if(l1->val < l2->val){              //以最小值更小的链表作为母链表
        small = l1;
        large = l2;
    } 
    else{
        small = l2;
        large = l1;
    }
    head = small;                       //head保存母链表首节点
    rear = small;                       //rear指向已经排好序的序列的尾节点
    small = small->next;                
    while(small && large){
        if(small->val >= large->val){
            l = large->next;            //暂存large的下一个节点指针
            large->next = rear->next;   //将large指向的节点插入母链表
            rear->next = large;
            rear = large;
            large = l;                  //large移动至下一个节点
        }
        else{
            rear = small;
            small = small->next;
        }
    }
    if(large)
        rear->next = large;
    return head;
}

分析

时间复杂度为线性级别，空间复杂度为常数级别。
此版本直接将一个链表作为母链表。另外一种做法是将两个链表中第一个值更小的那一个节点从原链表中断开，作为新链表的首节点，然后将这两个链表的节点插入这个新链表中。这样会更加易于处理。