21.合并两个有序链表

【LetMeFly】21.合并两个有序链表

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

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

 

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

 

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

方法一：遍历

使用一个指针p指向新的链表，

在list1和list2都非空时：

• 若$list1->val < list2->val$，则$p->next = list1, list1 = list1->next$

• 否则，$p->next = list2, list2 = list2->next$

• 无论如何都：$p = p->next$

• 时间复杂度$O(len(list1) + len(list2))$（其实为$\min(len(list1), len(list2))$

• 空间复杂度$O(1)$，力扣返回值不计入算法空间复杂度。（如果list1和list2允许修改的话，空间使用量将会更低）

AC代码

C++

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode();
        ListNode* p = head;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                p->next = list1;
                list1 = list1->next;
            }
            else {
                p->next = list2;
                // list2->=next; （笑）
                list2 = list2->next;
            }
            p = p->next;
        }
        if (list1) {
            p->next = list1;
        }
        else {
            p->next = list2;
        }
        return head->next;
    }
};

Python

# from typing import Optional

# # 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]:
        head = ListNode()
        p = head
        while list1 and list2:
            if list1.val < list2.val:
                p.next = list1
                list1 = list1.next
            else:
                p.next = list2
                list2 = list2.next
            p = p.next
        if list1:
            p.next = list1
        else:
            p.next = list2
        return head.next

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132115272