</br>

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.

</br>

Solution

Since there are two sorted linked lists, we only have to individually compare the value of two pointers in the correct order and assign the corresponding pointer to the merge list.

However, we have to notice that the definition of this linked list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

The definition does not provide us with the head node, hence instead of using head node and moving it around to compare the value of two lists, we have to implement the recursive method to achieve the goal.

The code is shown as below.

Java

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode mergeHead;
        
        if (l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        
        if(l1.val<l2.val){
            mergeHead = l1;
            mergeHead.next = mergeTwoLists(l1.next,l2);
        }
        else {
            mergeHead = l2;
            mergeHead.next = mergeTwoLists(l1,l2.next);
        }
        return mergeHead;
    }
}

</br>