By Long Luo

# Intuition

We can use Recursion to solve this problem.

The key points of Recursion are $$2$$.

1. How to terminate the recursion: Returns when either $$\texttt{l1}$$ or $$\texttt{l2}$$ is $$\texttt{null}$$.

2. 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.

# Image Explanation

You can get a intuition from below images.

## Analysis

• Time Complexity: $$O(m + n)$$.
• Space Complexity: $$O(m + n)$$.

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗