Merge Two Sorted Lists: Linked List

First Thoughts: construct a new linked list, with head node starting from whichever has a smaller value (not forgetting to update head node of altered argument linked list). every time a new node is added to return list, current advance. this comparison method only works if both of the nodes are not null. if one of the lists is "used up", just add all the nodes of the remaining list. be careful of the edge case, where one list is fully empty.

My solution:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode current1 = list1;
        ListNode current2 = list2;
        ListNode head;
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (current1.val<current2.val) {
            head = current1;
            current1 = current1.next;
        }
        else {
            head = current2;
            current2 = current2.next;
        }
        ListNode current = head;
        while (current1!=null && current2!=null) {
            if (current1.val<current2.val) {
                current.next = current1;
                current1 = current1.next;
            }
            else {
                current.next = current2;
                current2 = current2.next;
            }
            current = current.next;
        }
        while (current1!=null) {
            current.next = current1;
            current = current.next;
            current1 = current1.next;
        }
        while (current2!=null) {
            current.next = current2;
            current = current.next;
            current2 = current2.next;
        }
        
        return head;
    }
}

More Elegant Solution: using Recursion

Recursive thinking: sorted linked list is basically the smaller node of the two given linked lists (l1 and l2) + sorted linked list. base case is when one of the linked list is null (if either is null, return the other)

if (list1==null) return list2;
else if (list2==null) return list1;
else if (list1.val<list2.val) {
	list1.next = mergeTwoLists(list1.next, list2);
    return list1;
}
else {
	list2.next = mergeTwoLists(list1, list2.next);
    return list2;
}

Catch Point

1. Another possible solution can be reusing and reordering linked list, rather than constructing a new linked list from scratch.
2. Let function handle rest of the linked list to be sorted, take care of only the very first node -> be sure to specify base case.