1. Problem Statement

Given two sorted lists, merge them into a single sorted list.

Types of inputs:

1. Two sorted arrays (e.g., int[] nums1, int[] nums2)
2. Two sorted linked lists (e.g., ListNode list1, ListNode list2)

Part 1: Merge Two Sorted Arrays

Input:
nums1 = [1, 3, 5]
nums2 = [2, 4, 6]

Output:
[1, 2, 3, 4, 5, 6]

Approach: Two-Pointer Technique

• Use two pointers i and j for each array.
• Compare elements at those pointers.
• Append the smaller one to the result list.
• Move the corresponding pointer forward.
• Continue until both arrays are fully traversed.

Java Implementation

import java.util.*;

public class MergeSortedArrays {
    public static int[] merge(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] result = new int[m + n];
        int i = 0, j = 0, k = 0;

        // Traverse both arrays
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                result[k++] = nums1[i++];
            } else {
                result[k++] = nums2[j++];
            }
        }

        // Copy remaining elements
        while (i < m) {
            result[k++] = nums1[i++];
        }

        while (j < n) {
            result[k++] = nums2[j++];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 5};
        int[] nums2 = {2, 4, 6};
        int[] merged = merge(nums1, nums2);
        System.out.println(Arrays.toString(merged));
    }
}

Part 2: Merge Two Sorted Linked Lists

This is often asked in Linked List problems in interviews like at LeetCode.

Problem Example:

Input:
list1 = 1 -> 3 -> 5
list2 = 2 -> 4 -> 6

Output:
1 -> 2 -> 3 -> 4 -> 5 -> 6

Approach: Iterative Merge Using Dummy Node

• Create a dummy node to simplify pointer handling.
• Use a tail pointer to build the result list.
• Compare current nodes of both lists.
• Append the smaller one to the result and move the pointer.
• At the end, connect remaining nodes.

Java Code: Merge Two Sorted Linked Lists (Iterative)

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class MergeSortedLinkedLists {
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);  // dummy node
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        // Append remaining nodes
        if (list1 != null) tail.next = list1;
        if (list2 != null) tail.next = list2;

        return dummy.next;
    }

    // Utility method to print list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + (head.next != null ? " -> " : ""));
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Creating first sorted linked list: 1 -> 3 -> 5
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(3);
        list1.next.next = new ListNode(5);

        // Creating second sorted linked list: 2 -> 4 -> 6
        ListNode list2 = new ListNode(2);
        list2.next = new ListNode(4);
        list2.next.next = new ListNode(6);

        ListNode merged = mergeTwoLists(list1, list2);
        printList(merged); // Expected: 1 -> 2 -> 3 -> 4 -> 5 -> 6
    }
}

Visual Representation (Linked List Merge)

List 1: 1 -> 3 -> 5
List 2: 2 -> 4 -> 6

Step-by-step merge:
1 -> compare(1,2) -> pick 1
1 -> 2 -> compare(3,4) -> pick 2
1 -> 2 -> 3 -> pick 3
1 -> 2 -> 3 -> 4 -> pick 4
1 -> 2 -> 3 -> 4 -> 5 -> pick 5
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> pick 6 (done)