9

LeetCode: 21. Merge Two Sorted Lists

 3 years ago
source link: https://mozillazg.com/2020/10/leetcode-21-merge-two-sorted-lists.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目

原题地址：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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK