[LeetCode] Problem 21 - Merge Two Sorted Lists

Posted on | In ,

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

Code

1
2
3
4
5
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null)
        return l2;

    if (l2 == null)
        return l1;

    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
    else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}