What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Two Pointers & Sliding Window

P1EasyMental model~3 min speedrun

Two-Sequence Merge Pointers

The problem

Merge Two Sorted Lists (LC 21)(opens leetcode.com)

Two singly linked lists, list1 and list2, are each sorted from the smallest value to the largest. Equal values are allowed.

Join them into one list that is also sorted. Reuse the nodes that already exist: do not create new nodes to hold the values.

Return the head of the joined list. If both lists are empty, the answer is an empty list.

Example 1

Input:list1 = [1,2,4], list2 = [1,3,4]

Output:[1,1,2,3,4,4]

At every step the smaller of the two front values goes next. The two front values 1 and 1 are equal, so either node may go first; the result is the same.

list1

list2

Merge Two Sorted

two sorted sequences ➔ take the smaller head, move only its pointer ➔ drain the other sequence ➔ one pass

Spot it when: Two sorted arrays or lists must be read together in one pass: merged into one order, intersected, compared value by value, or joined at the values they share.

Merge Two Sorted

Python

1	from typing import Optional
2
3	class ListNode:
4	def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
5	self.val = val
6	self.next = next
7
8	def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
9	"""Merge Two Sorted Lists: relink the smaller head of the two lists, one node at a time.
10	Time: O(M + N) \| Space: O(1) extra
11	"""
12	# list1 and list2 are the two pointers: each one is the first unread node of its own list
13	dummy = ListNode(0) # Fake first node, so the first real node is attached like every other
14	tail = dummy # Last node of the merged list built so far
15
16	# 1. Take The Smaller Head:
17	# Both lists are sorted, so the smaller head is the smallest unread node of both. Attach it, then move only the pointer of the list it came from.
18	while list1 and list2:
19	if list1.val <= list2.val:
20	tail.next = list1
21	list1 = list1.next
22	else:
23	tail.next = list2
24	list2 = list2.next
25	tail = tail.next
26
27	# 2. Attach The Rest Of The Other List:
28	# The loop stops when one list is empty. The other list is already sorted and already linked, so one assignment attaches all of it.
29	tail.next = list1 if list1 else list2
30
31	# 3. Return The Node After The Dummy:
32	# dummy only marks the start, so the merged list begins at dummy.next.
33	return dummy.next

Invariant: The list from dummy.next to tail is sorted, and no unread node (from list1 or list2 on) is smaller than any node in it.

Each list is sorted, so its first unread node is its smallest, and the smaller of list1 and list2 is the smallest unread node of both lists: attach that node to tail and move only the pointer of the list it came from. The other pointer stays where it is, because its node is not smaller than the node just attached and still has to be compared with the next node of the other list. Each step attaches the smallest node that is left, so the merged list grows in sorted order and every node is attached exactly once. When list1.val equals list2.val, <= takes the node from list1 first, so equal values keep the order in which the two lists were given. The trap is the end of the loop: while list1 and list2 stops as soon as one list is empty, and the other list still holds unread nodes. Attach them with tail.next = list1 if list1 else list2, or every node after the last comparison is lost. Two arrays have no links to reuse, so they need a drain loop that copies the leftover values one by one.

See it run

Merge Two Sorted Lists: merge_two_lists([1, 2, 4, 9], [1, 3, 4])

list1 1list2 1merged []

The top row is list1, the middle row is list2, and the bottom row is the merged list. Cells are in list order.

list1 the first unread node of list1
list2 the first unread node of list2
tail the node just attached to the merged list
rest nodes of the other list attached in one assignment

Start: list1 is [1, 2, 4, 9] and list2 is [1, 3, 4]. The merged list is empty. Each pointer is at the first node of its list.

list1

1list1

list2

1list2

merged

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the attach of the other list after the loop
Mistake
```
# nothing after the loop
```
Fix
```
tail.next = list1 if list1 else list2
```
What happens: while list1 and list2 stops as soon as one list is empty. The other list still holds nodes that were never compared. Without the line tail.next = list1 if list1 else list2, tail.next stays None and those nodes are not in the result.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [1, 1, 2, 3, 4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 2: Looping while either list has a node
Mistake
```
while list1 or list2:
```
Fix
```
while list1 and list2:
```
What happens: Inside the loop, list1.val <= list2.val reads the val of both heads. When one list is empty, its pointer is None and None.val raises an error. The loop must stop when either list is empty, and the next line attaches the other list.
Example: list1 = [5], list2 = [1, 2, 6]
Mistake: raises AttributeErrorFix: returns [1, 2, 5, 6]
Gotcha 3: Using < so that a tie takes the node from list2
Mistake
```
if list1.val < list2.val:
```
Fix
```
if list1.val <= list2.val:
```
What happens: When both heads hold the same value, < is False, so the else branch attaches the node from list2 first. The values in the result are the same, but equal nodes from list1 now come after equal nodes from list2. This matters when each node carries more data than its value, because a stable merge keeps equal keys in the order the two lists were given.
Example: list1 = [1] (node a), list2 = [1] (node b)
Mistake: returns FalseFix: returns True
Gotcha 4: Forgetting to move tail after an attach
Mistake
```
pass
```
Fix
```
tail = tail.next
```
What happens: tail must always be the last node of the merged list. If it stays on dummy, every attach overwrites dummy.next, so each new node replaces the one attached before it. Only the node from the last assignment survives, together with the nodes that follow it in its own list.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 5: Returning dummy instead of dummy.next
Mistake
```
return dummy
```
Fix
```
return dummy.next
```
What happens: dummy is the fake node with value 0 that sits before the first real node. Returning dummy returns a list that starts with this extra 0, so the result is one node longer than the merge.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [0, 1, 1, 2, 3, 4, 4]Fix: returns [1, 1, 2, 3, 4, 4]

Not this one if…

The pair you want sits inside one sorted array and the two pointers start at its two ends, as in Two Sum II - Input Array Is Sorted (LC 167): there is no second sequence to walk beside the first. See Converging Pointers
There are k sorted lists instead of two, as in Merge k Sorted Lists (LC 23): picking the smallest head is no longer a single comparison. See K-Way Merge

Deep Dive

Why the smaller head is the next node of the answer

Each list is sorted from smallest to largest. So the first unread node of a list is the smallest unread node of that list. The code names these two nodes list1 and list2.

The smaller of list1.val and list2.val is therefore the smallest unread node of both lists. No unread node can be smaller. That node is the next node of the merged list.

The code attaches it with tail.next and moves tail to it. Then it moves only the pointer of the list that the node came from. The other pointer stays, because its node was not smaller and still has to be compared with the next node of the other list.

This repeats the same fact each time, so the merged list stays sorted. Every node is attached once, and no node is copied. The code only changes next links.

Tracing [1, 2, 4, 9] and [1, 3, 4]

The board shows the two lists and the merged list. The tags list1 and list2 show the first unread node of each list. The tag tail shows the node that was just attached.

The first step compares 1 and 1. The values are equal, and <= takes the node from list1. Then 2 is compared with 1, so the node 1 of list2 is attached. After that, 2 is smaller than 3, 3 is smaller than 4, and the two values 4 are equal, so list1 goes first.

In the last comparison, list1.val is 9 and list2.val is 4. The node 4 of list2 is attached. Now list2 is None, so while list1 and list2 stops. The merged list is [1, 1, 2, 3, 4, 4], and the node 9 has not been attached yet.

The line tail.next = list1 if list1 else list2 attaches 9 in one assignment. The result is [1, 1, 2, 3, 4, 4, 9]. The same code returns [1, 1, 2, 3, 4, 4] for [1, 2, 4] and [1, 3, 4], which is Example 1 of Merge Two Sorted Lists (LC 21).

The end of the loop, and equal values

The loop condition is while list1 and list2. It must stop when either list is empty, because the loop body reads list1.val and list2.val. A pointer that is None has no val.

When the loop stops, one list can still have nodes. In the trace, this is the node 9. Without the line after the loop, tail.next stays None, and these nodes are missing from the result. For the traced input the result would be [1, 1, 2, 3, 4, 4].

Because that list is sorted and already linked, one assignment attaches all of it. Two arrays have no links. A solution for arrays needs a second loop that copies the leftover values one by one. In Merge Sorted Array (LC 88), nums1 has free space at its end, so the merge writes from the back. The write position then never passes a value that is not read yet.

On a tie, list1.val <= list2.val takes the node from list1. Equal nodes then keep the order in which the lists were given. This is called a stable merge. It matters when a node has more data than its value.

The cost, and where the same walk appears

Every comparison attaches one node, and no pointer moves backward. A list of length M and a list of length N need at most M + N steps, so the time is O(M + N). The merge relinks the existing nodes, so the extra space is O(1). A merge of two arrays into a new array needs O(M + N) space.

The same walk, with a different action in each step, solves other problems on two sorted sequences. Interval List Intersections (LC 986) moves the pointer of the interval that ends first. Minimum Common Value (LC 2540) moves the pointer of the smaller value, and returns when both values are equal.

Merge k Sorted Lists (LC 23) has k lists. Finding the smallest of k heads is no longer one comparison, so it needs a different tool.

60-Second Pitch

"Both lists are sorted, so the first unread node of each list is its smallest. The smaller of the two is the smallest unread node overall. I use a dummy node and a tail. While both lists have nodes, I attach the smaller head to tail.next, move tail, and move only the pointer of that list. I use <= so equal values keep their input order. When one list ends, the other list is sorted and linked, so I attach it with one assignment. Then I return dummy.next. Every node is attached once. The time is O(M + N), and the extra space is O(1), because I only relink nodes."

Common Questions

What is the time and space complexity?: The time is O(M + N), because each comparison attaches one node and no pointer moves back. The extra space is O(1) for linked lists, because the nodes are relinked. A merge of two arrays into a new array uses O(M + N) space.
Why do you need a dummy node?: The first node of the merged list can come from either list, and it is not known before the first comparison. With dummy and tail, the first real node is attached like every other node. Without it, the code needs a separate case for the first node.
Why <= and not <?: The values in the result are the same. With <=, a node from list1 goes before an equal node from list2, so equal nodes keep the order in which the lists were given. This is a stable merge, and it matters when nodes carry more data than their value.
How would you merge two sorted arrays in place?: In Merge Sorted Array (LC 88), nums1 has free space at its end. Write the largest value first, at the last position, and move both read pointers from the back. The write position never passes a value that is not read yet.
What changes for k sorted lists?: Choosing the smallest of k heads is no longer one comparison. Merge k Sorted Lists (LC 23) keeps the k heads in a min-heap, which gives O(N log k) time for N nodes in total. Another way is to merge the lists in pairs.

SWE Reasoning

Spot it

The input is two sorted arrays or two sorted linked lists, and the answer needs both.
The problem asks for the merged order, the values the two sequences share, the first common value, or the overlap of two sorted lists of intervals.
One pass with O(1) extra space is expected, and a sort of the combined input is too slow or ignores the sorted order.

The invariant, step by step

dummy is a fake first node, and tail = dummy. list1 and list2 are the first unread nodes.
The merged list, from dummy.next to tail, is sorted. No unread node is smaller than any node in it.
while list1 and list2 compares the two heads. The smaller head is the smallest unread node of both lists.
tail.next takes that node, tail moves to it, and only the pointer of its own list moves. The invariant still holds.
When one list is empty, tail.next = list1 if list1 else list2 attaches the other list. It is sorted, and every node in it is not smaller than any node already attached.
return dummy.next returns the merged list.

Traps

No attach after the loop. The loop stops when one list is empty. The nodes of the other list are lost.
while list1 or list2. One pointer becomes None, and None.val raises an error.
< instead of <=. On a tie, the node from list2 is attached first, and the merge is no longer stable.
Not moving tail. Each attach replaces dummy.next, so only the last attached node survives.
return dummy. The result starts with the fake node 0.

Practice

Canonical LeetCode:Merge Two Sorted Lists (LC 21)Merge Sorted Array (LC 88)Get the Maximum Score (LC 1537)Interval List Intersections (LC 986)Minimum Common Value (LC 2540)Meeting Scheduler (LC 1229)

Theory Context•Two Pointers & Sliding Window

P1EasyMental model~3 min speedrun

Two-Sequence Merge Pointers

The problem

Merge Two Sorted Lists (LC 21)(opens leetcode.com)

Two singly linked lists, list1 and list2, are each sorted from the smallest value to the largest. Equal values are allowed.

Join them into one list that is also sorted. Reuse the nodes that already exist: do not create new nodes to hold the values.

Return the head of the joined list. If both lists are empty, the answer is an empty list.

Example 1

Input:list1 = [1,2,4], list2 = [1,3,4]

Output:[1,1,2,3,4,4]

At every step the smaller of the two front values goes next. The two front values 1 and 1 are equal, so either node may go first; the result is the same.

list1

list2

Merge Two Sorted

two sorted sequences ➔ take the smaller head, move only its pointer ➔ drain the other sequence ➔ one pass

Spot it when: Two sorted arrays or lists must be read together in one pass: merged into one order, intersected, compared value by value, or joined at the values they share.

Merge Two Sorted

Python

1	from typing import Optional
2
3	class ListNode:
4	def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
5	self.val = val
6	self.next = next
7
8	def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
9	"""Merge Two Sorted Lists: relink the smaller head of the two lists, one node at a time.
10	Time: O(M + N) \| Space: O(1) extra
11	"""
12	# list1 and list2 are the two pointers: each one is the first unread node of its own list
13	dummy = ListNode(0) # Fake first node, so the first real node is attached like every other
14	tail = dummy # Last node of the merged list built so far
15
16	# 1. Take The Smaller Head:
17	# Both lists are sorted, so the smaller head is the smallest unread node of both. Attach it, then move only the pointer of the list it came from.
18	while list1 and list2:
19	if list1.val <= list2.val:
20	tail.next = list1
21	list1 = list1.next
22	else:
23	tail.next = list2
24	list2 = list2.next
25	tail = tail.next
26
27	# 2. Attach The Rest Of The Other List:
28	# The loop stops when one list is empty. The other list is already sorted and already linked, so one assignment attaches all of it.
29	tail.next = list1 if list1 else list2
30
31	# 3. Return The Node After The Dummy:
32	# dummy only marks the start, so the merged list begins at dummy.next.
33	return dummy.next

Invariant: The list from dummy.next to tail is sorted, and no unread node (from list1 or list2 on) is smaller than any node in it.

See it run

Merge Two Sorted Lists: merge_two_lists([1, 2, 4, 9], [1, 3, 4])

list1 1list2 1merged []

The top row is list1, the middle row is list2, and the bottom row is the merged list. Cells are in list order.

list1 the first unread node of list1
list2 the first unread node of list2
tail the node just attached to the merged list
rest nodes of the other list attached in one assignment

Start: list1 is [1, 2, 4, 9] and list2 is [1, 3, 4]. The merged list is empty. Each pointer is at the first node of its list.

list1

1list1

list2

1list2

merged

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the attach of the other list after the loop
Mistake
```
# nothing after the loop
```
Fix
```
tail.next = list1 if list1 else list2
```
What happens: while list1 and list2 stops as soon as one list is empty. The other list still holds nodes that were never compared. Without the line tail.next = list1 if list1 else list2, tail.next stays None and those nodes are not in the result.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [1, 1, 2, 3, 4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 2: Looping while either list has a node
Mistake
```
while list1 or list2:
```
Fix
```
while list1 and list2:
```
What happens: Inside the loop, list1.val <= list2.val reads the val of both heads. When one list is empty, its pointer is None and None.val raises an error. The loop must stop when either list is empty, and the next line attaches the other list.
Example: list1 = [5], list2 = [1, 2, 6]
Mistake: raises AttributeErrorFix: returns [1, 2, 5, 6]
Gotcha 3: Using < so that a tie takes the node from list2
Mistake
```
if list1.val < list2.val:
```
Fix
```
if list1.val <= list2.val:
```
What happens: When both heads hold the same value, < is False, so the else branch attaches the node from list2 first. The values in the result are the same, but equal nodes from list1 now come after equal nodes from list2. This matters when each node carries more data than its value, because a stable merge keeps equal keys in the order the two lists were given.
Example: list1 = [1] (node a), list2 = [1] (node b)
Mistake: returns FalseFix: returns True
Gotcha 4: Forgetting to move tail after an attach
Mistake
```
pass
```
Fix
```
tail = tail.next
```
What happens: tail must always be the last node of the merged list. If it stays on dummy, every attach overwrites dummy.next, so each new node replaces the one attached before it. Only the node from the last assignment survives, together with the nodes that follow it in its own list.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 5: Returning dummy instead of dummy.next
Mistake
```
return dummy
```
Fix
```
return dummy.next
```
What happens: dummy is the fake node with value 0 that sits before the first real node. Returning dummy returns a list that starts with this extra 0, so the result is one node longer than the merge.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [0, 1, 1, 2, 3, 4, 4]Fix: returns [1, 1, 2, 3, 4, 4]

Not this one if…

The pair you want sits inside one sorted array and the two pointers start at its two ends, as in Two Sum II - Input Array Is Sorted (LC 167): there is no second sequence to walk beside the first. See Converging Pointers
There are k sorted lists instead of two, as in Merge k Sorted Lists (LC 23): picking the smallest head is no longer a single comparison. See K-Way Merge

Deep Dive

Why the smaller head is the next node of the answer

Each list is sorted from smallest to largest. So the first unread node of a list is the smallest unread node of that list. The code names these two nodes list1 and list2.

The smaller of list1.val and list2.val is therefore the smallest unread node of both lists. No unread node can be smaller. That node is the next node of the merged list.

This repeats the same fact each time, so the merged list stays sorted. Every node is attached once, and no node is copied. The code only changes next links.

Tracing [1, 2, 4, 9] and [1, 3, 4]

The board shows the two lists and the merged list. The tags list1 and list2 show the first unread node of each list. The tag tail shows the node that was just attached.

The end of the loop, and equal values

The loop condition is while list1 and list2. It must stop when either list is empty, because the loop body reads list1.val and list2.val. A pointer that is None has no val.

The cost, and where the same walk appears

Merge k Sorted Lists (LC 23) has k lists. Finding the smallest of k heads is no longer one comparison, so it needs a different tool.

60-Second Pitch

Common Questions

What is the time and space complexity?: The time is O(M + N), because each comparison attaches one node and no pointer moves back. The extra space is O(1) for linked lists, because the nodes are relinked. A merge of two arrays into a new array uses O(M + N) space.
Why do you need a dummy node?: The first node of the merged list can come from either list, and it is not known before the first comparison. With dummy and tail, the first real node is attached like every other node. Without it, the code needs a separate case for the first node.
Why <= and not <?: The values in the result are the same. With <=, a node from list1 goes before an equal node from list2, so equal nodes keep the order in which the lists were given. This is a stable merge, and it matters when nodes carry more data than their value.
How would you merge two sorted arrays in place?: In Merge Sorted Array (LC 88), nums1 has free space at its end. Write the largest value first, at the last position, and move both read pointers from the back. The write position never passes a value that is not read yet.
What changes for k sorted lists?: Choosing the smallest of k heads is no longer one comparison. Merge k Sorted Lists (LC 23) keeps the k heads in a min-heap, which gives O(N log k) time for N nodes in total. Another way is to merge the lists in pairs.

SWE Reasoning

Spot it

The input is two sorted arrays or two sorted linked lists, and the answer needs both.
The problem asks for the merged order, the values the two sequences share, the first common value, or the overlap of two sorted lists of intervals.
One pass with O(1) extra space is expected, and a sort of the combined input is too slow or ignores the sorted order.

The invariant, step by step

dummy is a fake first node, and tail = dummy. list1 and list2 are the first unread nodes.
The merged list, from dummy.next to tail, is sorted. No unread node is smaller than any node in it.
while list1 and list2 compares the two heads. The smaller head is the smallest unread node of both lists.
tail.next takes that node, tail moves to it, and only the pointer of its own list moves. The invariant still holds.
When one list is empty, tail.next = list1 if list1 else list2 attaches the other list. It is sorted, and every node in it is not smaller than any node already attached.
return dummy.next returns the merged list.

Traps

No attach after the loop. The loop stops when one list is empty. The nodes of the other list are lost.
while list1 or list2. One pointer becomes None, and None.val raises an error.
< instead of <=. On a tie, the node from list2 is attached first, and the merge is no longer stable.
Not moving tail. Each attach replaces dummy.next, so only the last attached node survives.
return dummy. The result starts with the fake node 0.

Practice

Canonical LeetCode:Merge Two Sorted Lists (LC 21)Merge Sorted Array (LC 88)Get the Maximum Score (LC 1537)Interval List Intersections (LC 986)Minimum Common Value (LC 2540)Meeting Scheduler (LC 1229)

Theory Context•Two Pointers & Sliding Window

P1EasyMental model~3 min speedrun

Two-Sequence Merge Pointers

The problem

Merge Two Sorted Lists (LC 21)(opens leetcode.com)

Two singly linked lists, list1 and list2, are each sorted from the smallest value to the largest. Equal values are allowed.

Join them into one list that is also sorted. Reuse the nodes that already exist: do not create new nodes to hold the values.

Return the head of the joined list. If both lists are empty, the answer is an empty list.

Example 1

Input:list1 = [1,2,4], list2 = [1,3,4]

Output:[1,1,2,3,4,4]

At every step the smaller of the two front values goes next. The two front values 1 and 1 are equal, so either node may go first; the result is the same.

list1

list2

Merge Two Sorted

two sorted sequences ➔ take the smaller head, move only its pointer ➔ drain the other sequence ➔ one pass

Spot it when: Two sorted arrays or lists must be read together in one pass: merged into one order, intersected, compared value by value, or joined at the values they share.

Merge Two Sorted

Python

1	from typing import Optional
2
3	class ListNode:
4	def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
5	self.val = val
6	self.next = next
7
8	def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
9	"""Merge Two Sorted Lists: relink the smaller head of the two lists, one node at a time.
10	Time: O(M + N) \| Space: O(1) extra
11	"""
12	# list1 and list2 are the two pointers: each one is the first unread node of its own list
13	dummy = ListNode(0) # Fake first node, so the first real node is attached like every other
14	tail = dummy # Last node of the merged list built so far
15
16	# 1. Take The Smaller Head:
17	# Both lists are sorted, so the smaller head is the smallest unread node of both. Attach it, then move only the pointer of the list it came from.
18	while list1 and list2:
19	if list1.val <= list2.val:
20	tail.next = list1
21	list1 = list1.next
22	else:
23	tail.next = list2
24	list2 = list2.next
25	tail = tail.next
26
27	# 2. Attach The Rest Of The Other List:
28	# The loop stops when one list is empty. The other list is already sorted and already linked, so one assignment attaches all of it.
29	tail.next = list1 if list1 else list2
30
31	# 3. Return The Node After The Dummy:
32	# dummy only marks the start, so the merged list begins at dummy.next.
33	return dummy.next

Invariant: The list from dummy.next to tail is sorted, and no unread node (from list1 or list2 on) is smaller than any node in it.

See it run

Merge Two Sorted Lists: merge_two_lists([1, 2, 4, 9], [1, 3, 4])

list1 1list2 1merged []

The top row is list1, the middle row is list2, and the bottom row is the merged list. Cells are in list order.

list1 the first unread node of list1
list2 the first unread node of list2
tail the node just attached to the merged list
rest nodes of the other list attached in one assignment

Start: list1 is [1, 2, 4, 9] and list2 is [1, 3, 4]. The merged list is empty. Each pointer is at the first node of its list.

list1

1list1

list2

1list2

merged

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the attach of the other list after the loop
Mistake
```
# nothing after the loop
```
Fix
```
tail.next = list1 if list1 else list2
```
What happens: while list1 and list2 stops as soon as one list is empty. The other list still holds nodes that were never compared. Without the line tail.next = list1 if list1 else list2, tail.next stays None and those nodes are not in the result.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [1, 1, 2, 3, 4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 2: Looping while either list has a node
Mistake
```
while list1 or list2:
```
Fix
```
while list1 and list2:
```
What happens: Inside the loop, list1.val <= list2.val reads the val of both heads. When one list is empty, its pointer is None and None.val raises an error. The loop must stop when either list is empty, and the next line attaches the other list.
Example: list1 = [5], list2 = [1, 2, 6]
Mistake: raises AttributeErrorFix: returns [1, 2, 5, 6]
Gotcha 3: Using < so that a tie takes the node from list2
Mistake
```
if list1.val < list2.val:
```
Fix
```
if list1.val <= list2.val:
```
What happens: When both heads hold the same value, < is False, so the else branch attaches the node from list2 first. The values in the result are the same, but equal nodes from list1 now come after equal nodes from list2. This matters when each node carries more data than its value, because a stable merge keeps equal keys in the order the two lists were given.
Example: list1 = [1] (node a), list2 = [1] (node b)
Mistake: returns FalseFix: returns True
Gotcha 4: Forgetting to move tail after an attach
Mistake
```
pass
```
Fix
```
tail = tail.next
```
What happens: tail must always be the last node of the merged list. If it stays on dummy, every attach overwrites dummy.next, so each new node replaces the one attached before it. Only the node from the last assignment survives, together with the nodes that follow it in its own list.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 5: Returning dummy instead of dummy.next
Mistake
```
return dummy
```
Fix
```
return dummy.next
```
What happens: dummy is the fake node with value 0 that sits before the first real node. Returning dummy returns a list that starts with this extra 0, so the result is one node longer than the merge.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [0, 1, 1, 2, 3, 4, 4]Fix: returns [1, 1, 2, 3, 4, 4]

Not this one if…

The pair you want sits inside one sorted array and the two pointers start at its two ends, as in Two Sum II - Input Array Is Sorted (LC 167): there is no second sequence to walk beside the first. See Converging Pointers
There are k sorted lists instead of two, as in Merge k Sorted Lists (LC 23): picking the smallest head is no longer a single comparison. See K-Way Merge

Deep Dive

Why the smaller head is the next node of the answer

Each list is sorted from smallest to largest. So the first unread node of a list is the smallest unread node of that list. The code names these two nodes list1 and list2.

The smaller of list1.val and list2.val is therefore the smallest unread node of both lists. No unread node can be smaller. That node is the next node of the merged list.

This repeats the same fact each time, so the merged list stays sorted. Every node is attached once, and no node is copied. The code only changes next links.

Tracing [1, 2, 4, 9] and [1, 3, 4]

The board shows the two lists and the merged list. The tags list1 and list2 show the first unread node of each list. The tag tail shows the node that was just attached.

The end of the loop, and equal values

The loop condition is while list1 and list2. It must stop when either list is empty, because the loop body reads list1.val and list2.val. A pointer that is None has no val.

The cost, and where the same walk appears

Merge k Sorted Lists (LC 23) has k lists. Finding the smallest of k heads is no longer one comparison, so it needs a different tool.

60-Second Pitch

Common Questions

What is the time and space complexity?: The time is O(M + N), because each comparison attaches one node and no pointer moves back. The extra space is O(1) for linked lists, because the nodes are relinked. A merge of two arrays into a new array uses O(M + N) space.
Why do you need a dummy node?: The first node of the merged list can come from either list, and it is not known before the first comparison. With dummy and tail, the first real node is attached like every other node. Without it, the code needs a separate case for the first node.
Why <= and not <?: The values in the result are the same. With <=, a node from list1 goes before an equal node from list2, so equal nodes keep the order in which the lists were given. This is a stable merge, and it matters when nodes carry more data than their value.
How would you merge two sorted arrays in place?: In Merge Sorted Array (LC 88), nums1 has free space at its end. Write the largest value first, at the last position, and move both read pointers from the back. The write position never passes a value that is not read yet.
What changes for k sorted lists?: Choosing the smallest of k heads is no longer one comparison. Merge k Sorted Lists (LC 23) keeps the k heads in a min-heap, which gives O(N log k) time for N nodes in total. Another way is to merge the lists in pairs.

SWE Reasoning

Spot it

The input is two sorted arrays or two sorted linked lists, and the answer needs both.
The problem asks for the merged order, the values the two sequences share, the first common value, or the overlap of two sorted lists of intervals.
One pass with O(1) extra space is expected, and a sort of the combined input is too slow or ignores the sorted order.

The invariant, step by step

dummy is a fake first node, and tail = dummy. list1 and list2 are the first unread nodes.
The merged list, from dummy.next to tail, is sorted. No unread node is smaller than any node in it.
while list1 and list2 compares the two heads. The smaller head is the smallest unread node of both lists.
tail.next takes that node, tail moves to it, and only the pointer of its own list moves. The invariant still holds.
When one list is empty, tail.next = list1 if list1 else list2 attaches the other list. It is sorted, and every node in it is not smaller than any node already attached.
return dummy.next returns the merged list.

Traps

No attach after the loop. The loop stops when one list is empty. The nodes of the other list are lost.
while list1 or list2. One pointer becomes None, and None.val raises an error.
< instead of <=. On a tie, the node from list2 is attached first, and the merge is no longer stable.
Not moving tail. Each attach replaces dummy.next, so only the last attached node survives.
return dummy. The result starts with the fake node 0.

Practice

Canonical LeetCode:Merge Two Sorted Lists (LC 21)Merge Sorted Array (LC 88)Get the Maximum Score (LC 1537)Interval List Intersections (LC 986)Minimum Common Value (LC 2540)Meeting Scheduler (LC 1229)

Theory Context•Two Pointers & Sliding Window

P1EasyMental model~3 min speedrun

Two-Sequence Merge Pointers

The problem

Merge Two Sorted Lists (LC 21)(opens leetcode.com)

Two singly linked lists, list1 and list2, are each sorted from the smallest value to the largest. Equal values are allowed.

Join them into one list that is also sorted. Reuse the nodes that already exist: do not create new nodes to hold the values.

Return the head of the joined list. If both lists are empty, the answer is an empty list.

Example 1

Input:list1 = [1,2,4], list2 = [1,3,4]

Output:[1,1,2,3,4,4]

At every step the smaller of the two front values goes next. The two front values 1 and 1 are equal, so either node may go first; the result is the same.

list1

list2

Merge Two Sorted

two sorted sequences ➔ take the smaller head, move only its pointer ➔ drain the other sequence ➔ one pass

Spot it when: Two sorted arrays or lists must be read together in one pass: merged into one order, intersected, compared value by value, or joined at the values they share.

Merge Two Sorted

Python

1	from typing import Optional
2
3	class ListNode:
4	def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
5	self.val = val
6	self.next = next
7
8	def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
9	"""Merge Two Sorted Lists: relink the smaller head of the two lists, one node at a time.
10	Time: O(M + N) \| Space: O(1) extra
11	"""
12	# list1 and list2 are the two pointers: each one is the first unread node of its own list
13	dummy = ListNode(0) # Fake first node, so the first real node is attached like every other
14	tail = dummy # Last node of the merged list built so far
15
16	# 1. Take The Smaller Head:
17	# Both lists are sorted, so the smaller head is the smallest unread node of both. Attach it, then move only the pointer of the list it came from.
18	while list1 and list2:
19	if list1.val <= list2.val:
20	tail.next = list1
21	list1 = list1.next
22	else:
23	tail.next = list2
24	list2 = list2.next
25	tail = tail.next
26
27	# 2. Attach The Rest Of The Other List:
28	# The loop stops when one list is empty. The other list is already sorted and already linked, so one assignment attaches all of it.
29	tail.next = list1 if list1 else list2
30
31	# 3. Return The Node After The Dummy:
32	# dummy only marks the start, so the merged list begins at dummy.next.
33	return dummy.next

Invariant: The list from dummy.next to tail is sorted, and no unread node (from list1 or list2 on) is smaller than any node in it.

See it run

Merge Two Sorted Lists: merge_two_lists([1, 2, 4, 9], [1, 3, 4])

list1 1list2 1merged []

The top row is list1, the middle row is list2, and the bottom row is the merged list. Cells are in list order.

list1 the first unread node of list1
list2 the first unread node of list2
tail the node just attached to the merged list
rest nodes of the other list attached in one assignment

Start: list1 is [1, 2, 4, 9] and list2 is [1, 3, 4]. The merged list is empty. Each pointer is at the first node of its list.

list1

1list1

list2

1list2

merged

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the attach of the other list after the loop
Mistake
```
# nothing after the loop
```
Fix
```
tail.next = list1 if list1 else list2
```
What happens: while list1 and list2 stops as soon as one list is empty. The other list still holds nodes that were never compared. Without the line tail.next = list1 if list1 else list2, tail.next stays None and those nodes are not in the result.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [1, 1, 2, 3, 4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 2: Looping while either list has a node
Mistake
```
while list1 or list2:
```
Fix
```
while list1 and list2:
```
What happens: Inside the loop, list1.val <= list2.val reads the val of both heads. When one list is empty, its pointer is None and None.val raises an error. The loop must stop when either list is empty, and the next line attaches the other list.
Example: list1 = [5], list2 = [1, 2, 6]
Mistake: raises AttributeErrorFix: returns [1, 2, 5, 6]
Gotcha 3: Using < so that a tie takes the node from list2
Mistake
```
if list1.val < list2.val:
```
Fix
```
if list1.val <= list2.val:
```
What happens: When both heads hold the same value, < is False, so the else branch attaches the node from list2 first. The values in the result are the same, but equal nodes from list1 now come after equal nodes from list2. This matters when each node carries more data than its value, because a stable merge keeps equal keys in the order the two lists were given.
Example: list1 = [1] (node a), list2 = [1] (node b)
Mistake: returns FalseFix: returns True
Gotcha 4: Forgetting to move tail after an attach
Mistake
```
pass
```
Fix
```
tail = tail.next
```
What happens: tail must always be the last node of the merged list. If it stays on dummy, every attach overwrites dummy.next, so each new node replaces the one attached before it. Only the node from the last assignment survives, together with the nodes that follow it in its own list.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [4]Fix: returns [1, 1, 2, 3, 4, 4]
Gotcha 5: Returning dummy instead of dummy.next
Mistake
```
return dummy
```
Fix
```
return dummy.next
```
What happens: dummy is the fake node with value 0 that sits before the first real node. Returning dummy returns a list that starts with this extra 0, so the result is one node longer than the merge.
Example: list1 = [1, 2, 4], list2 = [1, 3, 4]
Mistake: returns [0, 1, 1, 2, 3, 4, 4]Fix: returns [1, 1, 2, 3, 4, 4]

Not this one if…

The pair you want sits inside one sorted array and the two pointers start at its two ends, as in Two Sum II - Input Array Is Sorted (LC 167): there is no second sequence to walk beside the first. See Converging Pointers
There are k sorted lists instead of two, as in Merge k Sorted Lists (LC 23): picking the smallest head is no longer a single comparison. See K-Way Merge

Deep Dive

Why the smaller head is the next node of the answer

Each list is sorted from smallest to largest. So the first unread node of a list is the smallest unread node of that list. The code names these two nodes list1 and list2.

The smaller of list1.val and list2.val is therefore the smallest unread node of both lists. No unread node can be smaller. That node is the next node of the merged list.

This repeats the same fact each time, so the merged list stays sorted. Every node is attached once, and no node is copied. The code only changes next links.

Tracing [1, 2, 4, 9] and [1, 3, 4]

The board shows the two lists and the merged list. The tags list1 and list2 show the first unread node of each list. The tag tail shows the node that was just attached.

The end of the loop, and equal values

The loop condition is while list1 and list2. It must stop when either list is empty, because the loop body reads list1.val and list2.val. A pointer that is None has no val.

The cost, and where the same walk appears

Merge k Sorted Lists (LC 23) has k lists. Finding the smallest of k heads is no longer one comparison, so it needs a different tool.

60-Second Pitch

Common Questions

What is the time and space complexity?: The time is O(M + N), because each comparison attaches one node and no pointer moves back. The extra space is O(1) for linked lists, because the nodes are relinked. A merge of two arrays into a new array uses O(M + N) space.
Why do you need a dummy node?: The first node of the merged list can come from either list, and it is not known before the first comparison. With dummy and tail, the first real node is attached like every other node. Without it, the code needs a separate case for the first node.
Why <= and not <?: The values in the result are the same. With <=, a node from list1 goes before an equal node from list2, so equal nodes keep the order in which the lists were given. This is a stable merge, and it matters when nodes carry more data than their value.
How would you merge two sorted arrays in place?: In Merge Sorted Array (LC 88), nums1 has free space at its end. Write the largest value first, at the last position, and move both read pointers from the back. The write position never passes a value that is not read yet.
What changes for k sorted lists?: Choosing the smallest of k heads is no longer one comparison. Merge k Sorted Lists (LC 23) keeps the k heads in a min-heap, which gives O(N log k) time for N nodes in total. Another way is to merge the lists in pairs.

SWE Reasoning

Spot it

The input is two sorted arrays or two sorted linked lists, and the answer needs both.
The problem asks for the merged order, the values the two sequences share, the first common value, or the overlap of two sorted lists of intervals.
One pass with O(1) extra space is expected, and a sort of the combined input is too slow or ignores the sorted order.

The invariant, step by step

dummy is a fake first node, and tail = dummy. list1 and list2 are the first unread nodes.
The merged list, from dummy.next to tail, is sorted. No unread node is smaller than any node in it.
while list1 and list2 compares the two heads. The smaller head is the smallest unread node of both lists.
tail.next takes that node, tail moves to it, and only the pointer of its own list moves. The invariant still holds.
When one list is empty, tail.next = list1 if list1 else list2 attaches the other list. It is sorted, and every node in it is not smaller than any node already attached.
return dummy.next returns the merged list.

Traps

No attach after the loop. The loop stops when one list is empty. The nodes of the other list are lost.
while list1 or list2. One pointer becomes None, and None.val raises an error.
< instead of <=. On a tie, the node from list2 is attached first, and the merge is no longer stable.
Not moving tail. Each attach replaces dummy.next, so only the last attached node survives.
return dummy. The result starts with the fake node 0.

Practice

Canonical LeetCode:Merge Two Sorted Lists (LC 21)Merge Sorted Array (LC 88)Get the Maximum Score (LC 1537)Interval List Intersections (LC 986)Minimum Common Value (LC 2540)Meeting Scheduler (LC 1229)