Given 2 sorted linked lists, merge them into one in sorted order

Merge 2 Sorted Lists.md

Problem

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

---

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

---

Example 2:

Input: list1 = [], list2 = []
Output: []

---

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

---

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

mergeTwoLists-iterative.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) {
        ListNode dummyStartNode = new ListNode();
        ListNode mergedListTailNode = dummyStartNode;
        
        while (list1 != null && list2 != null) {
            
            if (list1.val < list2.val) {
                mergedListTailNode.next = list1;
                list1 = list1.next;
            }
            else {
                mergedListTailNode.next = list2;
                list2 = list2.next;
            }
            
            mergedListTailNode = mergedListTailNode.next;
        }
        
        if (list1 != null) {
            mergedListTailNode.next = list1;
        } else if (list2 != null) {
            mergedListTailNode.next = list2;
        }
        
        return dummyStartNode.next;
    }
}

mergeTwoLists-recursive.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) {
        
        // base cases
        if (list1 == null && list2 == null) { return null; }
        if (list1 == null) { return list2; } // if list1 is shorter than list2, point to remaning of list2
        if (list2 == null) { return list1; } // if list2 is shorter than list1, point to remaning of list1
        
        ListNode dummyStartNode = new ListNode();
        
        if (list1.val < list2.val) {
            dummyStartNode = list1;
            list1 = list1.next;
        } else {
            dummyStartNode = list2;
            list2 = list2.next;
        }
        
        dummyStartNode.next = mergeTwoLists(list1, list2);
        return dummyStartNode;
    }
}

mergeTwoLists-recursive.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # base cases
        if not list1 and not list2:
            return None
        if not list1:
            return list2
        if not list2:
            return list1
        
        merged_list_start_node = ListNode()
        if (list1.val < list2.val):
            merged_list_start_node = list1
            list1 = list1.next
        else:
            merged_list_start_node = list2
            list2 = list2.next
            
        merged_list_start_node.next = self.mergeTwoLists(list1, list2)
        return merged_list_start_node