LeetCode: 21. Merge Two Sorted Lists

题目

原题地址：https://leetcode.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example 1:

image

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both l1 and l2 are sorted in non-decreasing order.

解法

同时遍历两个链表，比较各个节点的值构建新的有序链表

思路如下：

  • 定义一个新的链表 dummy 然后通过两个指针同时遍历两个链表
  • 如果 A 链表当前节点值小于或等于 B 链表当前节点的值，则将新链表的 tail 指向 A 链表当前节点， A 的遍历指针移到下一个节点，B 保持不变
  • 如果 A 链表当前节点值大于 B 链表当前节点的值，则将新链表的 tail 指向 B 链表当前节点， B 的遍历指针移到下一个节点，A 保持不变
  • 如果 A 的遍历指针到了链表最后位置无法再移动了，直接把新链表的 tail 指向 B 链表当前节点（因为 B 是个有序链表所以不需要再对 B 继续处理）
  • 如果 B 的遍历指针到了链表最后位置无法再移动了，直接把新链表的 tail 指向 A 链表当前节点（因为 B 是个有序链表所以不需要再对 A 继续处理）

这个方法的 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, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        dummy = ListNode()
        tail = dummy

        while l1 is not None and l2 is not None:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next

            tail = tail.next
            if l1 is None:
                tail.next = l2
            if l2 is None:
                tail.next = l1

        return dummy.next

Comments