Merge Two Sorted Lists - Java Solution

1. Introduction

This blog post addresses the "Merge Two Sorted Lists" problem, a fundamental task in linked list manipulation. The objective is to merge two sorted linked lists into a single sorted list. This problem tests the understanding of linked list operations and is a common question in data structure interviews.

Problem

Given the heads of two sorted linked lists list1 and list2, the task is to merge these lists into one sorted list. The final merged list should be made by splicing together the nodes of the first two lists and should be returned.

2. Solution Steps

1. Create a dummy head node to simplify the merge process.

2. Use a pointer, current, to track the current position for adding new nodes.

3. Compare the nodes of the two lists, adding the smaller one to current.

4. Advance current and the list from which the node was taken.

5. Repeat steps 3 and 4 until one of the lists is fully traversed.

6. Attach the remaining part of the non-empty list to current.

7. Return the merged list starting from the next node of the dummy head.

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeTwoSortedLists {
    public static void main(String[] args) {
        // Example use case
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(4);

        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        ListNode result = mergeTwoLists(list1, list2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    // Function to merge two sorted linked lists
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        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;
        }

        // Attach the remaining part of the list, if any
        current.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

Output:

1 1 2 3 4 4

Explanation:

1. mergeTwoLists: This function merges two sorted linked lists list1 and list2.

2. A dummy node is used to simplify the merge operation and handle edge cases.

3. The function iterates through both lists, comparing their current nodes. It attaches the smaller node to the merged list and advances the pointer in the corresponding list.

4. The loop continues until one of the lists is completely traversed.

5. The remaining nodes from the non-empty list (if any) are then attached to the merged list.

6. The function returns the merged list, which is the next node after the dummy, effectively skipping the dummy node.

7. This approach ensures that the merged list is sorted, preserving the order of the nodes from the input lists.