Leetcode

21. Merge Two Sorted Lists

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

Example 1:

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.

Solution1: Iteratively

class Solution:
def mergeTwoLists1(self, l1, l2):
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
# TC: O(m+n), where m, n are the lengths of the two linked lists
# SC: O(1)

Solution2: Recursively

class Solution:
def mergeTwoLists2(self, l1, l2):
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists2(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists2(l1, l2.next)
return l2
# TC: O(m+n)
# SC: O(m+n)

Solution3:in-place Iteratively

class Solution:
def mergeTwoLists(self, l1, l2):
if None in (l1, l2):
return l1 or l2
dummy = cur = ListNode(0)
dummy.next = l1
while l1 and l2:
if l1.val < l2.val:
l1 = l1.next
else:
nxt = cur.next
cur.next = l2
tmp = l2.next
l2.next = nxt
l2 = tmp
cur = cur.next
cur.next = l1 or l2
return dummy.next
# TC: O(m+n)
# SC: O(1)

Link

--

--

--

My homepage to record my thought processes for solving SQL and Algorithm questions

Recommended from Medium

Everything you need to know about Docker

Netcode Concepts Part 1: Introduction

Clean Architecture with Kotlin

The Encyclopedia of Online Coding Platforms — a killer new book that’s FREE (or darn near)

Six Reasons Why Your External Drive May Get Slow

Listening to Events in Hardhat using Ethers.js

Kafka Commands and Utilities

Space Shooter 2D Project Setup

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Isabelle

Isabelle

In love with telling stories with data

More from Medium

Leetcode Blind 75 Practice-Maximum Subarray

LeetCode 227

1155. Number of Dice Rolls With Target Sum

Solve Top LeetCode Problem Smartly