In this LeetCode challenge, we’re given two sorted LinkedLists, and asked to merge them in order. So, given two LinkedLists with the values
[1, 3, 5] and
[2, 4, 6], we should return a new LinkedList with values
[1, 2, 3, 4, 5, 6].
Solution #1: While loop
In this fairly classic approach to a comparison question, we start by creating a while loop. This loop will run for as long as both LinkedLists contain a node, and in each iteration will compare the two available nodes, take the lower one, and finally move that LinkedList along to its next entry.
Once the loop is broken, the remaining elements of whichever LinkedList is not empty are then appended to the end of the new LinkedList (as there are no remaining values in the other LinkedList for them to be compared against).
Solution #2: Recursion
LeetCode user yangliguang posted a great recursion approach, which I have expanded upon below. It does essentially the same thing as the while loop, but in a much more concise way. It can actually be simplified to just 4 lines, but of course that’s only at the expense of some readability.