MergeTwoLists_Approach-I.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null || list2 == null){
            return list1 == null ? list2 : list1;
        }

        if(list1.val > list2.val){
            ListNode tmp = list1;
            list1 = list2;
            list2 = tmp;
        }

        list1.next = mergeTwoLists(list1.next, list2);

        return list1;
    }
}