← all entries
A-036● Day 362026.06.11easyleetcode #21neetcode150

Merge Two Sorted Lists

#linked-list#recursion
↗ leetcode #21 · merge-two-sorted-lists
01

Problem

· problem
P.036

Merge Two Sorted Lists

↗ leetcode #21

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.

constraints
  • · Number of nodes in both lists: [0, 50]
  • · -100 ≤ Node.val ≤ 100
  • · Both lists are sorted in non-decreasing order
// paraphrased summary — see source for full text
examples
example 1input → output
[1,2,4]
[1,3,4]
[1,1,2,3,4,4]
example 2input → output
[]
[]
[]
example 3input → output
[]
[0]
[0]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Do we need to create new nodes or rearrange existing ones?
  • ☐
    What should we return if both lists are empty?
  • ☐
    Can the lists contain duplicate values?
  • ☐
    Are the input lists guaranteed to be sorted?
  • ☐
    Can we modify the original lists?
  • ☐
    Do we need to sort the merged list after combining?
  • ☐
    Should we allocate extra nodes for the merged list?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize dummy node
○
dummy = node = ListNode()
○
dummy = ListNode(0)
○
node = None
step 2· Loop while both lists have nodes
○
while list1 and list2:
○
while list1 or list2:
○
while True:
step 3· Compare and attach the smaller value│ nested
○
if list1.val < list2.val:
○
if list1.val <= list2.val:
○
if list1.val > list2.val:
step 4· Advance the merged list pointer│ nested
○
node = node.next
○
dummy = dummy.next
○
node.next = node.next.next
step 5· Attach remaining nodes
○
node.next = list1 or list2
○
return list1 or list2
○
node.next = list1 + list2
step 6· Return the merged list head
○
return dummy.next
○
return dummy
○
return node
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, val=0, next=None):
4
#         self.val = val
5
#         self.next = next
6
7
# Iterative
8
class Solution:
9
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
10
        dummy = node = ListNode()
11
12
        while list1 and list2:
13
            if list1.val < list2.val:
14
                node.next = list1
15
                list1 = list1.next
16
            else:
17
                node.next = list2
18
                list2 = list2.next
19
            node = node.next
20
21
        node.next = list1 or list2
22
23
        return dummy.next
24
    
25
# Recursive
26
class Solution:
27
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
28
        if not list1:
29
            return list2
30
        if not list2:
31
            return list1
32
        lil, big = (list1, list2) if list1.val < list2.val else (list2, list1)
33
        lil.next = self.mergeTwoLists(lil.next, big)
34
        return lil
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[1,2,4]
[1,3,4]
→
[1,1,2,3,4,4]
case 2
[]
[]
→
[]
case 3
[]
[0]
→
[0]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.