Merge Two Sorted Lists

class Solution {
public:
    ListNode* combineLists(ListNode* list1, ListNode* list2) {
        ListNode dummyNode(-1);
        ListNode* tail = &dummyNode;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 == nullptr ? list2 : list1;
        return dummyNode.next;
    }
};

The Merge Two Sorted Lists problem aims to merge two pre-sorted linked lists into a single, sorted linked list. The provided C++ solution implements a function named combineLists that takes two pointers to the heads of two sorted linked lists as parameters.

Here's a breakdown of the approach:

• Create a dummy node to act as the start of the new linked list, which helps in simplifying the insertion process.
• A pointer tail is used to keep track of the last node in the merged list.
• Iterate through both lists in a while loop until the end of one of them is reached. During each iteration, compare the node values from both lists:
  • Attach the node with the smaller value to the tail of the merged list.
  • Advance the tail pointer to this newly added node.
• Once one of the lists is exhausted, point the next node of tail to the non-null head of the remaining list. This step effectively appends the remainder of the non-exhausted list to the merged list.
• Finally, return the node next to the dummy node, as dummyNode.next represents the head of the newly merged list.

This solution ensures a linear time complexity relative to the total number of elements in both lists, making it efficient for merging lists where all elements must be evaluated. Furthermore, no additional space is allocated for list nodes; only a few pointers are used, achieving O(1) additional space complexity.

class Solution {
    public ListNode combineTwoLists(ListNode first, ListNode second) {
        ListNode dummyHead = new ListNode(-1);
        ListNode current = dummyHead;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                current.next = first;
                first = first.next;
            } else {
                current.next = second;
                second = second.next;
            }
            current = current.next;
        }

        current.next = first == null ? second : first;

        return dummyHead.next;
    }
}

The provided Java code demonstrates a solution for merging two sorted linked lists into one sorted linked list. The method combineTwoLists takes two linked lists first and second as its parameters. It employs a dummy head node to simplify the link establishment for the resultant merged list.

Here's a breakdown of the strategy used:

• Start by creating a "dummy" node with a placeholder value. This node acts as the preliminary head of the resulting merged list and helps in handling edge cases seamlessly.
• Use a pointer current initialized to the dummy node. This pointer helps in building the new merged list.
• A while loop continues until the end of either input list is reached. Within this loop:
  • Compare the current node values of first and second.
  • Attach the smaller node to current.next and advance the pointer (first or second) of the smaller node to the next node.
  • Move the current pointer to current.next, effectively growing the merged list.
• Once the loop completes, attach the remainder of the non-null list to current.next. This step handles the case where the lists are of unequal lengths.
• Return the merged list starting from the node next to the dummy head, skipping over the dummy node used for initial setup.

The approach ensures that the merged list is sorted, effectively combining the elements of the two input lists while maintaining order, with a time complexity of O(n + m) and space complexity of O(1), where n and m are the respective lengths of the two input lists. This method balances simplicity and efficiency, making it an effective solution for the merging of two sorted lists.

struct ListNode* combineLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummyHead;
    dummyHead.val = -1;
    struct ListNode* current = &dummyHead;
    while (list1 != NULL && list2 != NULL) {
        if (list1->val <= list2->val) {
            current->next = list1;
            list1 = list1->next;
        } else {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next;
    }
    current->next = list1 == NULL ? list2 : list1;
    return dummyHead.next;
}

The provided code in C is a solution to merging two sorted linked lists into a single sorted linked list. Here's a concise summary of the process:

Define a function combineLists that takes two sorted linked lists (list1 and list2) as inputs.

• Initialize a dummy head node dummyHead with a placeholder value to facilitate easy list manipulation and track the head of the merged list.
• A pointer current points to the dummyHead to help in building the new list.
• Utilize a while loop to traverse both lists, comparing the current node values of list1 and list2. Attach the smaller node to the current node's next pointer and move the respective list pointer to the next node.
• Once one of the lists is completely traversed (either list1 or list2 becomes NULL), directly append the remaining part of the non-empty list to current.
• Finally, since dummyHead was an auxiliary node, the merged list actually starts from dummyHead.next. Thus, return dummyHead.next as the head of the merged list.

This method efficiently combines two sorted linked lists with linear complexity relative to the total number of elements, maintaining the sorted order without any additional space, except for variables.

function concatenateLists(list1, list2) {
    let initialNode = new ListNode(-1);
    let current = initialNode;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    current.next = list1 !== null ? list1 : list2;
    return initialNode.next;
}

The provided JavaScript function named concatenateLists merges two sorted linked lists into a single sorted linked list. This functional solution follows a standard merge algorithm from merge sort, particularly adapted for linked lists. Here's a breakdown of how this function operates:

• Initializes an initial node initialNode with a dummy value to simplify edge cases and manages the merge process, preventing the need to handle special cases for the head of the list during node connections.
• A current pointer is used to keep track of the last node in the merged list as the function progresses.
• A while loop runs as long as there are nodes remaining in both list1 and list2. Inside the loop:
  • Compares the values of the current nodes of list1 and list2.
  • Attaches the smaller value node to the next of current and progresses in the list from which the node was taken (either list1 or list2).
  • Moves the current pointer forward to the newly added node.
• After the loop, if one of the lists still has nodes left (meaning one list was longer), the remaining elements are all already sorted and can be directly linked to the merged list. This happens outside the loop using a ternary operator to attach the remainder of the non-null list (list1 or list2) to the current.next.
• The function returns initialNode.next, which points to the head of the newly merged sorted list, effectively skipping over the dummy initial node used for ease of implementation.

This concise approach ensures the merged list remains sorted, handling each element of the input lists exactly once, giving a linear runtime in relation to the combined size of the input lists. This solution is both efficient and practical for merging sorted linked lists.

class Solution:
    def combineLists(self, first, second):
        dummy = ListNode(-1)

        current = dummy
        while first and second:
            if first.val <= second.val:
                current.next = first
                first = first.next
            else:
                current.next = second
                second = second.next
            current = current.next

        current.next = first if first else second

        return dummy.next

This Python solution merges two pre-sorted linked lists into a single sorted linked list. The approach uses a dummy node to facilitate easier list manipulations and avoid handling special cases for the head node separately.

• Start by initializing a dummy node with an arbitrary value.
• Maintain a pointer current to track and build the merged list, starting from the dummy node.
• Use a while loop to iterate through both lists until one of them is exhausted. At each step:
  • Compare the current values of the two nodes pointed by first and second.
  • Attach the smaller value node to the current node.
  • Advance the current pointer and the pointer of the list from which the node was taken.
• Once out of the loop, link the remainder of the non-exhausted list (if any) to the end of the merged list.
• The merged list starts from the node following the dummy node, so return dummy.next.

This method effectively handles lists of different lengths and lists containing duplicate values, ensuring the merged result remains sorted.