LeetCode problem 21 Merge Two Sorted Lists(Java)

Source url:https://leetcode.com/problems/merge-two-sorted-lists/

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.