Merge two sorted linked lists

JavaView on GFG

Time: O(n+m)

Space: O(1)

Intuition

Use a dummy head. Compare heads of both lists, append smaller, advance that list's pointer.

Algorithm

1Create dummy node. curr = dummy.
2While both lists non-null: compare heads, append smaller to curr.next, advance pointer.
3Append remaining non-null list.
4Return dummy.next.

Common Pitfalls

•Don't forget to attach the remaining list after one list is exhausted.

Merge two sorted linked lists.java

Java

// Approach: Two-pointer merge: compare heads, attach smaller, advance its pointer. Handle remaining.
// Time: O(n+m) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {
    Node sortedMerge(Node head1, Node head2) {
        Node temp1 = head1;
        Node temp2 = head2;

        Node ans = new Node(0);
        Node head = ans;
        while (temp1 != null && temp2 != null) {
            if (temp1.data < temp2.data) {
                head.next = temp1;
                head = head.next;
                temp1 = temp1.next;
            } else {
                head.next = temp2;
                head = head.next;
                temp2 = temp2.next;
            }
        }

        if (temp1 != null)
            head.next = temp1;

        if (temp2 != null)
            head.next = temp2;

        return ans.next;
    }
}

Was this solution helpful?