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.
Input: 1->2->4, 1->3->4
This problem has a straightforward approach. We can traverse both linked lists at the same time. Every turn we choose the smaller one and move the corresponding linked list to the next node. In the process, if one of linked list is empty, then put another linked list to the tail of the result linked list.
This is the code:
And we can use recursion to make the code easier and clearer. First, if one of linked list is empty, then return another linked list. Then if the current first node of l1 is smaller than or equal with l2, we change the second node of l1 to the result of the origin second node of l1 merge with l2, vice-versa.
code download url：https://github.com/tinyfool/leetcode/tree/master/src/p0021