# Leetcode

Published in

2 min readJun 18, 2021

--

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)