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.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Plain Text
복사
Example 2:
Input: list1 = [], list2 = []
Output: []
Plain Text
복사
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Plain Text
복사
Constraints:
•
The number of nodes in both lists is in the range [0, 50].
•
100 <= Node.val <= 100
•
Both list1 and list2 are sorted in non-decreasing order.
When I first read the problem, it looked like it was simply asking to merge two lists and sort them in ascending order. But I wondered why it explicitly mentioned a linked list, so I figured I should take a closer look at the problem’s intent.
10 hours later…
As I kept reading, a few cautions stood out. It’s not just about merging two lists; they have to be merged as a linked list. So let’s first be clear on what a linked list is: it’s a structure where each node holds a reference (pointer) to the next node.
# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
Python
복사
And when looking at the problem, I don’t think they would provide a separate class called ListNode without reason. There must certainly be a specific role for that class.
Since it’s commented out, I’m not sure whether it’s meant just for reference or if I should uncomment it and actually use the class. At this point, I think we need to get some hints from our universal teacher, Google.
According to Google, when merging two sorted linked lists, a dummy node is needed. Then why is a dummy node necessary?
When merging two sorted lists, a dummy node is used to simplify the code. Normally, when merging lists, you first need to decide from which list to take the first node, and this step requires special handling.
The reason is that once the head, which is the starting point of the merged result list, is set, all subsequent nodes are always connected based on that head. In other words, until the first node is determined, the head itself is empty, so you can’t simply connect to head.next; it must be explicitly initialized first.
However, by creating a dummy node, this inconvenience can be resolved. The dummy node is a temporary node unrelated to actual data, providing a virtual starting point at the front of the result list. As a result, during the merging process, there’s no need to worry about whether it’s the first node or not—you can simply attach each new node after the current one.
At the end, returning the dummy node’s next gives you the actual starting node of the merged list. In the end, the dummy node elegantly eliminates the need for special handling of the first node and serves as a convenient technique that enables list merging with a consistent logic.
In the given problem, when list1 and list2 are passed in as parameters, they come in as instances of the pre-defined ListNode class. In other words, list1 and list2 are object types, and being object types means they represent nodes.
That is, when using the mergeTwoLists function externally, you must pass list1 and list2 as parameters of the ListNode class type. In other words, you need to pass the head nodes of already created linked list objects as list1 and list2 in the parameters.
So, in order to visually check the result, I wrote code that executes the mergeTwoLists function externally using the examples provided in the problem. By doing so, I can print the results to the console and observe the process of how the two lists are merged.
Test code in local area
from typing import Optional
# Definition for singly-linked list node
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Class for merging two sorted linked lists
class Solution:
def mergeTwoLists(
self, list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode(0) # Dummy node as the starting point
cur = dummy
# Traverse both lists and connect nodes in ascending order
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
# Attach the remaining nodes
cur.next = list1 or list2
return dummy.next # Return the real head
# ====== Test Code ======
# Helper function to convert a Python list into a Linked List
def build_linked_list(values):
dummy = ListNode(0)
cur = dummy
for v in values:
cur.next = ListNode(v)
cur = cur.next
return dummy.next # Return head node
# Helper function to print a Linked List
def print_linked_list(head):
while head:
print(head.val, end=" -> ")
head = head.next
print("None")
# Input lists
list1 = build_linked_list([1, 2, 4])
list2 = build_linked_list([1, 3, 4])
# Run Solution
solution = Solution()
merged = solution.mergeTwoLists(list1, list2)
# Print result
print_linked_list(merged)
Python
복사
The test code ended up being a bit long, but let’s take a look at what role each function plays and what operations they perform.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Python
복사
•
Role : Defines the node structure of a singly linked list.
•
Operation
◦
val: The value stored in the node (e.g., 1, 2, 3 …).
◦
next: A pointer (reference) to the next node.
◦
A linked list is a structure where multiple ListNode objects are connected like a chain through next.
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0) # Dummy node as the starting point
cur = dummy
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 or list2
return dummy.next # Real head
Python
복사
•
Role : Merges two sorted linked lists into one sorted linked list.
•
Operation
1.
Create a dummy node to mark the starting point (this makes handling the head easier).
2.
Use a cur pointer, comparing list1 and list2 and linking the smaller value.
3.
When one of the lists reaches the end (None), attach the remaining list to cur.next.
4.
Finally, return dummy.next → the actual head node of the result list.
def build_linked_list(values):
dummy = ListNode(0)
cur = dummy
for v in values:
cur.next = ListNode(v)
cur = cur.next
return dummy.next # Return head node
Python
복사
•
Role : Convert a Python list into a linked list.
•
Operation
1.
Create a dummy node.
2.
Iterate through each value v in the list, create a new ListNode(v), and connect it to cur.next.
3.
Move the cur pointer forward one step at a time while building the entire linked list.
4.
Since the real head is at dummy.next, return it.
Example : [1, 2, 4] → 1 -> 2 -> 4 -> None
During this loop, each ListNode object is created and assigned its own unique memory address. That address is then stored in the next variable inside the previous object, thereby linking the nodes together.
def print_linked_list(head):
while head:
print(head.val, end=" -> ")
head = head.next
print("None")
Python
복사
•
Role : Print the linked list in a human-readable format.
•
Operation
1.
Start from the head and print head.val.
2.
Move with head = head.next while traversing to the end.
3.
When the list ends, print None to indicate the termination point.
Example output
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None
Bash
복사
Frist try
from typing import Optional
# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0) # Dummy node as the starting point
cur = dummy
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 or list2
return dummy.next # Real head
Python
복사
I submitted the test cases, and fortunately, they all passed. Now I will go ahead and submit the final solution.
My solution was accepted. This problem was labeled as easy, but I honestly don’t quite understand why it’s considered easy. However, solving it gave me a great opportunity to implement a linked list in code, which I had only understood in theory until now.