[LeetCode][21. Merge Two Sorted Lists] The Recursive Algorithm with Detailed Image Explanation
By Long Luo
This article is the solution The Recursive Algorithm with Detailed Image Explanation of Problem 21. Merge Two Sorted Lists.
Intuition
We can use Recursion to solve this problem.
The key points of Recursion are \(2\).
How to terminate the recursion: Returns when either \(\texttt{l1}\) or \(\texttt{l2}\) is \(\texttt{null}\).
What to do in the process: if \(\texttt{l1.val} \le \texttt{l2.val}\), then point \(\texttt{l1.next}\) to the smaller of \(\texttt{l1}\) and \(\texttt{l2}\).
If \(\texttt{l1.val} \le \texttt{l2.val}\), we can choose the smaller node, such as \(\texttt{l1}\). However, the linked list is not reached the end, we will continue to compare.
Now we are compare \(\texttt{l1.next}\) and \(\texttt{l2}\). The \(\texttt{l1.next}\) and \(\texttt{l2}\) are processed in the recursive functions of the next layer.
We process such process and finally get the result.