Click here to go back to LeetCode summary page.
Problem description is here, or as follows:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Both solutions work with space complexity of O(1). Solution 1 uses a pointer and grows the resulting list by picking the current minimum value node in List 1 and List 2. Solution 2 merges List 2 into List 1 but inserting the smaller value node before the node in List 1. Both solutions are easy to understand, although Solution 1 appears to be more intuitive in my personal opinion.
This solution can be used as a subroutine in other problems, such as the “Sort List” problem.