Merge Two Sorted linked list problem and solution in Java and Python

“Merge Two Sorted Lists” is a classic linked list problem frequently asked in FAANG interviews. The idea is to merge two sorted linked lists into one sorted linked list.

I’ll show both Java and Python solutions.

1️⃣ Java – Merge Two Sorted Lists (Iterative)

class ListNode {
    int val;
    ListNode next;

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

public class MergeSortedLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // dummy node to simplify code
        ListNode tail = dummy;

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

        // attach remaining nodes
        if (l1 != null) tail.next = l1;
        if (l2 != null) tail.next = l2;

        return dummy.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        ListNode merged = mergeTwoLists(l1, l2);
        printList(merged); // Output: 1 2 3 4 5 6
    }
}

2️⃣ Python – Merge Two Sorted Lists (Iterative)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    return dummy.next

# Helper function to print list
def print_list(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

# Example
l1 = ListNode(1, ListNode(3, ListNode(5)))
l2 = ListNode(2, ListNode(4, ListNode(6)))

merged = merge_two_lists(l1, l2)
print_list(merged)  # Output: 1 2 3 4 5 6

⚡ Key Points

1. Use a dummy node to simplify edge cases.
2. Iterative approach is O(n + m) time, O(1) space.
3. There’s also a recursive approach:

Python recursive version:

def merge_recursive(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = merge_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_recursive(l1, l2.next)
        return l2