题目链接： https://leetcode.cn/problems/merge-two-sorted-lists/

视频题解： https://www.bilibili.com/video/BV17w4m1Y7CJ/

LeetCode 21. 合并两个有序链表

题目描述

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

举个例子：

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

视频讲解

建议大家点击视频跳转到b站合并两个有序链表 (opens new window)观看，体验更佳！

思路解析

本题的思路比较简单。创建一个虚拟节点newHead，定义一个始终指向新链表尾部的指针tail。

1. 当链表指针l1和l2都不为空，如果l1->val <= l2->val，就把l1指向的节点挂到tail后面，同时把l1往后移动一步，tail也向后移动一步。反之对于l2->val <= l1->val亦然。
2. 当链表指针l1或l2为空，把不为空的l1或l2挂到tail后面，返回newHead->next。

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //创建一个虚拟的头节点方便后面操作
        ListNode* newHead = new ListNode();
        ListNode* tail = newHead;
        while (list1 && list2) {
            //选取val较小的节点放到tail后面
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            //保证tail一直指向新链表的最后一个节点
            tail = tail->next;
        }
        //把剩下的有序节点挂到tail后面
        if (list1) {
            tail->next = list1;
        } else if (list2) {
            tail->next = list2;
        }
        return newHead->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) {
        // 创建一个虚拟的头节点方便后面操作
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while (list1 != null && list2 != null) {
            // 选取val较小的节点放到tail后面
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            // 保证tail一直指向新链表的最后一个节点
            tail = tail.next;
        }
        // 把剩下的有序节点挂到tail后面
        if (list1 != null) {
            tail.next = list1;
        } else if (list2 != null) {
            tail.next = list2;
        }
        return newHead.next;
    }
}

python代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 创建一个虚拟的头节点方便后面操作
        newHead = ListNode()
        tail = newHead
        while list1 and list2:
            # 选取val较小的节点放到tail后面
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            # 保证tail一直指向新链表的最后一个节点
            tail = tail.next
        # 把剩下的有序节点挂到tail后面
        if list1:
            tail.next = list1
        elif list2:
            tail.next = list2
        return newHead.next

复杂度分析

时间复杂度： O(m+n)，其中m是链表l1的长度，n是链表l2的长度。

空间复杂度： O(1)。