XTY的小站
记录技术笔记和技术博客

21. Merge Two Sorted List

05 Jul 2024

21. Merge Two Sorted List (Easy) 合并有序链表

题干

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

img

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

解法

朴素解法

# 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]:
        pre = ListNode()
        tail = pre

        while list1 is not None and list2 is not None:
            if list1.val > list2.val:
                tail.next = list2
                list2 = list2.next
            else:
                tail.next = list1
                list1 = list1.next
            tail = tail.next
        tail.next = list1 if list1 is not None else list2
        return pre.next
  • 使用一个pre节点，避免了处理第一个节点的特殊情况
  • while循环只处理两个链表都没到尾部的情况，其他一个到尾部时单独处理，这样避免了重复判断None的语句。