【题目描述】 将两个升序链表（l1 和 l2 均按非递减顺序排列）合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例2： 输入：l1 = [ ], l2 = [ ] 输出：[ ]

示例3： 输入：l1 = [ ], l2 = [0] 输出：[0]

无哨兵位的迭代解法

【基本思路】 在两个按非递减顺序排列的链表之间不断选择尾插较小值的节点，从而合并为一个新的按非递减顺序排列的链表。

【代码实现】

typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
          
   
    if (l1 == NULL)  // 如果l1是空链表
		return l2;

	if (l2 == NULL)  // 如果l2是空链表
		return l1;

    // 取两链表中较小值的头节点做新链表的头节点
	ListNode* head = NULL;
	if (l1->val < l2->val)   
	{
          
   
		head = l1;
		l1 = l1->next;
	}
	else
	{
          
   
		head = l2;
		l2 = l2->next;
	}

    // 不断取较小值的节点尾插在新链表上
	ListNode* tail = head;
	while (l1 && l2)
	{
          
   
		if (l1->val < l2->val)
		{
          
   
			tail->next = l1;
			l1 = l1->next;
		}
		else 
		{
          
   
			tail->next = l2;
			l2 = l2->next;
		}

		tail = tail->next;
	}

    // 最后必有某个原链表还剩下一串链表节点，直接尾插在新链表上
	if (l1)
		tail->next = l1;
		
	if (l2)
		tail->next = l2;

	return head;
}

有哨兵位的迭代解法

【基本思路】 借用哨兵位对上面的解法做了一下优化，其基本思路不变。

【代码实现】

typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
          
   
    if (l1 == NULL)  // 如果l1是空链表
        return l2;

    if (l2 == NULL)  // 如果l2是空链表
        return l1;
	
    ListNode* head = NULL;
    head = (ListNode*)malloc(sizeof(ListNode));  // 设置哨兵位
	ListNode* tail = head;
    while (l1 && l2)  // 不断取较小值的节点尾插在新链表上
    {
          
   
        if (l1->val < l2->val)
        {
          
   
            tail->next = l1;
            l1 = l1->next;
        }
        else 
        {
          
   
            tail->next = l2;
            l2 = l2->next;
        }

        tail = tail->next;
    }
	
	// 最后必有某个原链表还剩下一串链表节点，直接尾插在新链表上
    if (l1)
        tail->next = l1;

    if (l2)
        tail->next = l2;
	
	// 注意：新链表的真正的第一个节点是哨兵位的下一个节点
    ListNode* first = head->next;
    free(head);
    
    return first;
}

【复杂度分析】 时间复杂度：O(M + N)，其中 M 和 N 分别为两个链表的长度。 空间复杂度：O(1)。

【类似题目】

本专栏

其它专栏