L21 Merge two sorted Lists

recursion

Problem

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

Solution

Recursion O(n+m) since each recursive call increments the pointer to p1 or p2 by one, there will be exactly one call to the function per element in each list.

public ListNode mergeTwo(ListNode p1, ListNode p2){
    if(p1 == null) return p2;
    if(p2 == null) return p1;
    if(p1.val < p2.val){
        p1.next = mergeTwo(p1.next, p2);
        return p1;
    }else{
        p2.next = mergeTwo(p2.next, p1);
        return p2;
    }
}