Merge Two Sorted Linked Lists - Java Solution

1. Introduction

In this blog post, we'll delve into a common algorithmic problem in the realm of data structures: merging two sorted linked lists in Java. This problem is a must in programming interviews and is crucial for understanding how to manipulate and merge linked lists.

Problem

Given two sorted linked lists, the goal is to merge them into a single, sorted linked list. The final merged list should also be sorted.

Example:

Input:

1->2->4,

1->3->4

Output:

1->1->2->3->4->4

2. Solution Steps

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

2. Use two pointers, each pointing to the head of the two lists.

3. Compare the node values where the pointers are currently pointing.

4. Append the smaller value to the merged list and move the pointer of that list forward.

5. Continue the process until one of the lists is completely traversed.

6. Append the remaining part of the non-empty list to the merged list.

7. Return the next node of the dummy head as the head of the merged list.

3. Code Program

public class ListNode {
    int val; // Value of the node
    ListNode next; // Reference to the next node

    // Constructor to initialize the node with a value
    ListNode(int x) { val = x; }

    // Method to print the linked list starting from this node
    void printList() {
        ListNode temp = this;
        while(temp != null) {
            System.out.print(temp.val + " "); // Print the value of the current node
            temp = temp.next; // Move to the next node
        }
        System.out.println();
    }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // Dummy head to simplify list manipulation
        ListNode current = dummyHead; // Pointer to build the new list

        // Iterate as long as both lists have nodes
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) { // Compare values of the two nodes
                current.next = l1; // Link the smaller node
                l1 = l1.next; // Move forward in list l1
            } else {
                current.next = l2; // Link the smaller node
                l2 = l2.next; // Move forward in list l2
            }
            current = current.next; // Move to the next node in the merged list
        }

        // Link the remaining part of the list that is not null
        current.next = (l1 != null) ? l1 : l2;

        return dummyHead.next; // Return the merged list, excluding the dummy head
    }
}

// Example usage and testing
public class Main {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1); // First node of first list
        l1.next = new ListNode(2); // Second node of first list
        l1.next.next = new ListNode(4); // Third node of first list

        ListNode l2 = new ListNode(1); // First node of second list
        l2.next = new ListNode(3); // Second node of second list
        l2.next.next = new ListNode(4); // Third node of second list

        Solution solution = new Solution();
        ListNode mergedList = solution.mergeTwoLists(l1, l2);
        mergedList.printList(); // Print the merged list
    }
}

Output:

1 1 2 3 4 4

Explanation:

The input lists are 1->2->4 and 1->3->4. 

The mergeTwoLists method merges these two lists by comparing the nodes of each list and appending the smaller node to the merged list. 

The process continues until all nodes in both lists are merged, resulting in the sorted output 1->1->2->3->4->4.