What is the Merging Sorted Singly Linked Lists Algorithm?

Merging sorted singly linked lists is a fundamental algorithm used to combine two sorted linked lists into one sorted list. It is commonly applied in problems requiring merging sequences or as part of more complex algorithms, such as merge sort.

The algorithm uses a two-pointer technique to traverse the lists and merge them efficiently while maintaining their sorted order.

The Technical View

• Time Complexity: (O(n + m))

  • Where (n) is the number of nodes in the first list, and (m) is the number of nodes in the second list. Each node is visited once, resulting in linear time complexity.

• Space Complexity: (O(1))

  • The algorithm uses constant space, as no extra data structures are required. The pointers traverse the existing nodes without duplicating them.

How It Works

The algorithm works by comparing the current nodes of both linked lists and appending the smaller node to a new merged list. It continues until all nodes from both lists are processed.

1. Initialization:

   • Create a dummy node to simplify the merging logic.
   • Use a pointer (current) to track the last node in the merged list.

2. Iterative Merge:

   • Traverse both linked lists:
     • Compare the current nodes.
     • Append the smaller node to the merged list and move the pointer in the corresponding list.

3. Appending Remaining Nodes:

   • If one list is exhausted, append the remaining nodes from the other list to the merged list.

4. Return Result:

   • Return the merged list starting from the node after the dummy node.

A Fifth-Grader's Summary

Imagine you have two sorted lines of people, one sorted by age and the other by height. You want to combine them into a single line sorted by age and then height. Start from the front of both lines and pick the person who comes first in the sorting order. Repeat until everyone is in one line. That’s how merging sorted linked lists works!

Real-World Example

Consider merging two sorted employee records, one based on joining dates and the other based on salary. Instead of sorting them from scratch, you can merge the records efficiently using this algorithm.

Algorithm with Code, Detailed Iterations, and Optimized Patterns

1. Merging Two Sorted Singly Linked Lists

Problem: Merge two sorted singly linked lists into one sorted list.

Code:

public class ListNode
{
    public int Value;
    public ListNode Next;

    public ListNode(int value = 0, ListNode next = null)
    {
        Value = value;
        Next = next;
    }
}

public static ListNode MergeTwoSortedLists(ListNode list1, ListNode list2)
{
    // Create a dummy node to simplify the merging logic
    ListNode dummy = new ListNode();
    ListNode current = dummy;

    // Traverse both lists
    while (list1 != null && list2 != null)
    {
        if (list1.Value <= list2.Value)
        {
            current.Next = list1;
            list1 = list1.Next;
        }
        else
        {
            current.Next = list2;
            list2 = list2.Next;
        }
        current = current.Next;
    }

    // Append the remaining nodes from either list
    current.Next = list1 ?? list2;

    // Return the merged list starting after the dummy node
    return dummy.Next;
}

What Happens in Each Iteration?

1. Initialization:

   • A dummy node is created as the starting point for the merged list.
   • current points to the last node in the merged list (initially dummy).

2. Iteration:

   • Compare the current nodes of list1 and list2:
     • If list1.Value <= list2.Value, add list1's node to the merged list.
     • Otherwise, add list2's node to the merged list.
   • Advance the pointer (list1 or list2) of the list from which a node was added.
   • Move current to the last node in the merged list.

3. Finalization:

   • When one list is exhausted, append the remaining nodes of the other list to the merged list.

Example Execution

Input:

• List 1: (1 -> 3 —>5)
• List 2: (2 —> 4 —>6)

Step-by-Step Execution:

1. Initialization:

   • dummy: (0)
   • current: (dummy)

2. First Iteration:

   • Compare (1) (list1) and (2) (list2).
   • Append (1) to the merged list.
   • Move list1 to (3).
   • Update current to (1).

Merged List: (1)

1. Second Iteration:
   • Compare (3) (list1) and (2) (list2).
   • Append (2) to the merged list.
   • Move list2 to (4).
   • Update current to (2).

Merged List: (1 —> 2)

1. Third Iteration:
   • Compare (3) (list1) and (4) (list2).
   • Append (3) to the merged list.
   • Move list1 to (5).
   • Update current to (3).

Merged List: (1 —> 2 —> 3)

1. Continue:

   • Repeat the process until one list is exhausted.

2. Finalization:

   • Append the remaining nodes from list2 ((4 —> 6)) to the merged list.

Merged List: (1 —> 2 —> 3 —> 4 —> 5 —> 6)

Result:

Merged List: (1 —> 2 —> 3 —> 4 —> 5 —> 6)

Advantages and Disadvantages

Advantages:

1. Efficient with (O(n + m)) time complexity.
2. Simple to implement with constant space complexity.
3. Works seamlessly for arbitrarily long linked lists.

Disadvantages:

1. Requires sorted input lists; unsorted lists must be sorted first.
2. In-place modification of input lists may not always be desirable.

Conclusion

The algorithm for merging sorted singly linked lists is both efficient and elegant, providing a solution to combine two ordered sequences with minimal overhead. Its importance extends beyond linked lists, forming the foundation of other algorithms like merge sort. By mastering this technique, you enhance your understanding of both linked lists and divide-and-conquer strategies!