Simple merge
Input
[1, 3, 5], [2, 4, 6]
Output
[1, 2, 3, 4, 5, 6]
Merging two sorted lists interleaves their elements in ascending order.
Full lesson preview
Merge two sorted lists
Merge two sorted singly linked lists into a single sorted list and return it as a Python list.
Python practice14 minLinked ListsIntermediateLast updated March 27, 2026
Problem statement
You are given two sorted singly linked lists (ascending). Merge them into a single sorted linked list and return the result as a Python list. Inputs will be provided as Python lists representing node values; you should convert them to linked lists internally, perform the merge, and return a Python list of values from the merged linked list.
Requirements:
- Preserve all values from both lists in non-decreasing order.
- Do not use Python's sort to combine the lists; perform a proper merge of two sorted linked lists.
- Time complexity: O(n + m), where n and m are lengths of the input lists.
When either input list is empty, return the other list's values.
Task
Implement merging of two sorted linked lists with O(n) time and O(1) additional node allocations (aside from building input lists).
Examples
Input format
Two Python lists representing sorted linked lists, e.g., [1, 3, 5], [2, 4].
Output format
A Python list with merged values in ascending order.
Constraints
- Values are integers. Lists may be empty. Aim for O(n + m) time and O(1) additional linked-list pointers.
Samples
Sample 1
Input
[1, 2, 3], []
Output
[1, 2, 3]
Second list is empty, so the merged result is the first list.