Search⌘ K
Home
Courses
An In-Depth Understanding of Memory and Pointers in C

Practice: Sorted Union

Explore how to combine two sorted linked lists into one sorted list without altering the original lists. Understand the intercalation algorithm and local references technique to achieve this efficiently with a single traversal, mastering key linked list manipulation skills in C.

We'll cover the following...

Problem statement

The input consists of two lists in sorted order, and we must construct a new list to represent the reunion of the two lists. The reunion must maintain the sorted order. The two input lists must remain unchanged.

We can only traverse each list at most once. That is, the complexity should be O(n)O(n). We can’t merge the two lists and then sort the result. We have to exploit the fact that the input lists are in sorted order.

For example, given the following:

list1 = [1, 3, 5, 10]
list2 = [0, 2, 6, 22, 23, 24, 25]

The reunion in sorted order is as follows:

reunion = [0, 1, 2, 3, 5, 6, 10, 22, 23, 24, 25]

We must solve this problem using local references.

Solution

We present a clever algorithm called intercalation to solve this problem. It can help us combine the two sorted lists ...