Merge Two Sorted Linked Lists in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

struct Node {
    int val;
    struct Node* next;
};

struct Node* merge(struct Node* l1, struct Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

C Output

Input: 1→3→5 and 2→4→6  
Output: 1→2→3→4→5→6

C++ Program

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

Node* merge(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

C++ Output

Input: 1→2→4 and 3→5  
Output: 1→2→3→4→5

JAVA Program

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

Node merge(Node l1, Node l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    } else {
        l2.next = merge(l1, l2.next);
        return l2;
    }
}

JAVA Output

Input: 1→3 and 2→4→5  
Output: 1→2→3→4→5

Python Program

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

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

Python Output

Input: 1→3→5 and 2→4→6  
Output: 1→2→3→4→5→6

In-Depth Explanation

Example

Suppose you have two sorted linked lists:

List A: 1 → 3 → 5

List B: 2 → 4 → 6

To combine them, we compare the first ones: 1 < 2, so 1 remains. Next, compare 3 and 2: 2 follows. Next compare 3 and 4: 3 remains. We continue doing this until both lists are fully merged into: 1 → 2 → 3 → 4 → 5 → 6.

Real-Life Analogy

Consider two checkout lines for a grocery store in which the items are already sorted by cost. You want to form one line that is sorted. You consider the head of each line and swap the one with the cheaper item to the new line. Do this again and again until both lines are exhausted.

This is how you merge: always take the smaller head and move ahead.

Why It Matters

Combining sorted lists is one of the most basic operations in data structure. It is the foundation of more complex sorting algorithms such as Merge Sort, which employs this very method for merging sorted sublists. It is also extensively applied in multi-way data merge, stream processing, and combining user information from various sources in web systems.

What You Learn from This

You gain recursive thinking, pointer manipulation, and linear merging efficiently. The logic is also clean: it merely requires constant space (when written iteratively) or O(n) space using recursion because of the call stack. You also know how to construct new lists from current nodes without unnecessary memory allocation.

Interview Relevance and Real Projects

This is a popular interview question — particularly at entry and mid-level. Variants involve combining K sorted arrays, eliminating duplicates during combination, or combination in-place. In software practice, this logic is useful when combining sorted logs, database query result sets, version histories, and search engine data from various indexes.

SEO-Optimized Explanation

Sorting two sorted linked lists is an important algorithm that merges two pre-sorted lists into a single sorted list based on efficient pointer redirection. It is basic for becoming proficient in linked list management and is widely applied in merge sort, data stream merging, and real-time system data aggregation. By practising this logic in C, C++, Java, and Python, beginners gain the confidence to work with recursion, loops, and dynamic memory constructs. This issue is also a common scenario in coding interviews, as it evaluates algorithmic readability, optimisation, and comprehension of linear data structures used in contemporary applications.