Merging Multiple Linked Lists into a Single Linked List
Merging multiple linked lists involves combining two or more linked lists into a single, consolidated linked list. This operation is crucial for efficiently managing and manipulating large data which requires frequent regrouping or reordering. One example use case is in text editors, where text is often represented as a collection of linked lists (e.g., one list per line or paragraph) and these lists are merged when converting the document to plain text or when performing operations like search and replace across the entire document.
Note that the merging we discuss here is different from merging of sorted linked lists. In our current problem, the merged linked list need not be in sorted order.
The problem of merging multiple linked lists involves combining two or more separate linked lists into a single, unified linked list. This operation should preserve the original order of elements within each list while ensuring that all the nodes from all the linked lists are connected together.
Examples
Input-1:
List 1: 1 -> 3 -> 5
List 2: 2 -> 4 -> 6
List 3: 7 -> 8 -> 9
Expected Output-1:
1 -> 3 -> 5 -> 2 -> 4 -> 6 -> 7 -> 8 -> 9
Input-2:
List 1: A -> C -> E
List 2: B -> D -> F
Expected Output-2:
A -> C -> E -> B -> D -> F
Constraints and Assumptions
We assume that we only have access to the head node of each list, not the tail node.
The merging process does not involve sorting the elements. The goal is to just combine the lists while maintaining the original order in each list.
The linked lists may have different lengths.
There are no loops within the input lists.
Memory efficiency should be considered, avoiding unnecessary copying of nodes when possible.
Different Approaches
Sequential Approach
Below is the algorithm for merging multiple linked lists using sequential approach:
Start with the first list as the base for the merged list.
Initialize a current pointer to the head of the merged list.
For each remaining list:
Traverse the merged list using the ‘current’ pointer until reaching its tail (i.e., until current.next is null).
Connect this tail to the head of the next list by setting current.next to the head of the next list.
Update current to point to the head of the newly added list.
Repeat steps 3 until all lists are merged.
# Definition for singly-linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to merge k linked lists
def merge_k_lists(lists):
# Check if the input list is empty
if not lists:
return None
# Start with the first list as the base for the merged list
merged = lists[0]
# Iterate through the remaining lists
for i in range(1, len(lists)):
# If the current list is empty, continue to the next one
if not lists[i]:
continue
# If the merged list is empty, set it to the current list
if not merged:
merged = lists[i]
continue
# Initialize the current pointer to the head of the merged list
current = merged
# Traverse to the end of the merged list
while current.next:
current = current.next
# Connect the tail of the merged list to the head of the next list
current.next = lists[i]
return merged
# Helper function to create a linked list from a Python list
def create_linked_list(arr):
if not arr:
return None
head = Node(arr[0])
current = head
for val in arr[1:]:
current.next = Node(val)
current = current.next
return head
# Helper function to print a linked list
def print_linked_list(head):
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage
list1 = create_linked_list([1, 4, 5])
list2 = create_linked_list([1, 3, 4])
list3 = create_linked_list([2, 6])
lists = [list1, list2, list3]
merged = merge_k_lists(lists)
print("Merged list:")
print_linked_list(merged)
#include <stdio.h>
#include <stdlib.h>
// Definition for singly-linked list node
struct Node {
int data;
struct Node* next;
};
// Function to merge k linked lists
struct Node* merge_k_lists(struct Node** lists, int k) {
// Check if the input list is empty
if (k == 0) {
return NULL;
}
// Start with the first list as the base for the merged list
struct Node* merged = lists[0];
// Iterate through the remaining lists
for (int i = 1; i < k; i++) {
// If the current list is empty, continue to the next one
if (lists[i] == NULL) {
continue;
}
// If the merged list is empty, set it to the current list
if (merged == NULL) {
merged = lists[i];
continue;
}
// Initialize the current pointer to the head of the merged list
struct Node* current = merged;
// Traverse to the end of the merged list
while (current->next != NULL) {
current = current->next;
}
// Connect the tail of the merged list to the head of the next list
current->next = lists[i];
}
return merged;
}
// Helper function to create a linked list from an array
struct Node* create_linked_list(int* arr, int size) {
if (size == 0) {
return NULL;
}
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = arr[0];
head->next = NULL;
struct Node* current = head;
for (int i = 1; i < size; i++) {
current->next = (struct Node*)malloc(sizeof(struct Node));
current = current->next;
current->data = arr[i];
current->next = NULL;
}
return head;
}
// Helper function to print a linked list
void print_linked_list(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
// Example usage
int arr1[] = {1, 4, 5};
int arr2[] = {1, 3, 4};
int arr3[] = {2, 6};
struct Node* list1 = create_linked_list(arr1, 3);
struct Node* list2 = create_linked_list(arr2, 3);
struct Node* list3 = create_linked_list(arr3, 2);
struct Node* lists[] = {list1, list2, list3};
int k = 3; // Number of lists
struct Node* merged = merge_k_lists(lists, k);
printf("Merged list:\n");
print_linked_list(merged);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
// Definition for singly-linked list node
class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Function to merge k linked lists
Node* merge_k_lists(vector<Node*>& lists) {
// Check if the input list is empty
if (lists.empty()) {
return nullptr;
}
// Start with the first list as the base for the merged list
Node* merged = lists[0];
// Iterate through the remaining lists
for (int i = 1; i < lists.size(); i++) {
// If the current list is empty, continue to the next one
if (!lists[i]) {
continue;
}
// If the merged list is empty, set it to the current list
if (!merged) {
merged = lists[i];
continue;
}
// Initialize the current pointer to the head of the merged list
Node* current = merged;
// Traverse to the end of the merged list
while (current->next) {
current = current->next;
}
// Connect the tail of the merged list to the head of the next list
current->next = lists[i];
}
return merged;
}
// Helper function to create a linked list from a vector
Node* create_linked_list(vector<int>& arr) {
if (arr.empty()) {
return nullptr;
}
Node* head = new Node(arr[0]);
Node* current = head;
for (int i = 1; i < arr.size(); i++) {
current->next = new Node(arr[i]);
current = current->next;
}
return head;
}
// Helper function to print a linked list
void print_linked_list(Node* head) {
Node* current = head;
while (current) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
int main() {
// Example usage
vector<int> arr1 = {1, 4, 5};
vector<int> arr2 = {1, 3, 4};
vector<int> arr3 = {2, 6};
Node* list1 = create_linked_list(arr1);
Node* list2 = create_linked_list(arr2);
Node* list3 = create_linked_list(arr3);
vector<Node*> lists = {list1, list2, list3};
Node* merged = merge_k_lists(lists);
cout << "Merged list:" << endl;
print_linked_list(merged);
return 0;
}
// Definition for singly-linked list node
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Function to merge k linked lists
function mergeKLists(lists) {
// Check if the input list is empty
if (!lists || lists.length === 0) {
return null;
}
// Start with the first list as the base for the merged list
let merged = lists[0];
// Iterate through the remaining lists
for (let i = 1; i < lists.length; i++) {
// If the current list is empty, continue to the next one
if (!lists[i]) {
continue;
}
// If the merged list is empty, set it to the current list
if (!merged) {
merged = lists[i];
continue;
}
// Initialize the current pointer to the head of the merged list
let current = merged;
// Traverse to the end of the merged list
while (current.next) {
current = current.next;
}
// Connect the tail of the merged list to the head of the next list
current.next = lists[i];
}
return merged;
}
// Helper function to create a linked list from a JavaScript array
function createLinkedList(arr) {
if (!arr || arr.length === 0) {
return null;
}
const head = new Node(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Helper function to print a linked list
function printLinkedList(head) {
let current = head;
let result = '';
while (current) {
result += current.data + ' -> ';
current = current.next;
}
result += 'null';
console.log(result);
}
// Example usage
const list1 = createLinkedList([1, 4, 5]);
const list2 = createLinkedList([1, 3, 4]);
const list3 = createLinkedList([2, 6]);
const lists = [list1, list2, list3];
const merged = mergeKLists(lists);
console.log("Merged list:");
printLinkedList(merged);
import java.util.ArrayList;
import java.util.List;
public class Main {
// Definition for singly-linked list node
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Function to merge k linked lists
public static Node mergeKLists(List<Node> lists) {
// Check if the input list is empty
if (lists == null || lists.isEmpty()) {
return null;
}
// Start with the first list as the base for the merged list
Node merged = lists.get(0);
// Iterate through the remaining lists
for (int i = 1; i < lists.size(); i++) {
// If the current list is empty, continue to the next one
if (lists.get(i) == null) {
continue;
}
// If the merged list is empty, set it to the current list
if (merged == null) {
merged = lists.get(i);
continue;
}
// Initialize the current pointer to the head of the merged list
Node current = merged;
// Traverse to the end of the merged list
while (current.next != null) {
current = current.next;
}
// Connect the tail of the merged list to the head of the next list
current.next = lists.get(i);
}
return merged;
}
// Helper function to create a linked list from a Java array
public static Node createLinkedList(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
Node head = new Node(arr[0]);
Node current = head;
for (int i = 1; i < arr.length; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Helper function to print a linked list
public static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// Example usage
Node list1 = createLinkedList(new int[]{1, 4, 5});
Node list2 = createLinkedList(new int[]{1, 3, 4});
Node list3 = createLinkedList(new int[]{2, 6});
List<Node> lists = new ArrayList<>();
lists.add(list1);
lists.add(list2);
lists.add(list3);
Node merged = mergeKLists(lists);
System.out.println("Merged list:");
printLinkedList(merged);
}
}
Time and Space Complexity:
Time Complexity: O(n), where n is the total number of nodes across all lists.
Space Complexity: O(1), as we only use a constant amount of extra space.
Advantages and Disadvantages:
Advantages:
Simple to implement
Memory efficient
Disadvantages:
May not be optimal for a large number of lists
Recursive Approach
The recursive approach to merging multiple linked lists involves recursively combining pairs of lists until all lists are merged. Here’s the algorithm:
If there’s only one list or no lists, return that list or null respectively.
If there are two or more lists:
Recursively merge the first half of the lists.
Recursively merge the second half of the lists.
Merge the two resulting lists.
To merge two lists:
If one list is empty, return the other list.
Otherwise, connect the tail of first list with the head node of second list.
# Definition for singly-linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to merge k linked lists recursively
def merge_k_lists(lists):
# Base case: if the list is empty, return None
if not lists:
return None
# Base case: if there's only one list, return it
if len(lists) == 1:
return lists[0]
# Divide the lists into two halves
mid = len(lists) // 2
left = merge_k_lists(lists[:mid])
right = merge_k_lists(lists[mid:])
# Merge the two halves
return merge_two_lists(left, right)
# Helper function to merge two linked lists
def merge_two_lists(l1, l2):
# Base cases: if one list is empty, return the other
if not l1:
return l2
if not l2:
return l1
# Find tail node of list1 and connect it to head of list2
current = l1
while current.next:
current = current.next
current.next = l2
return l1
# Helper function to create a linked list from a Python list
def create_linked_list(arr):
if not arr:
return None
head = Node(arr[0])
current = head
for val in arr[1:]:
current.next = Node(val)
current = current.next
return head
# Helper function to print a linked list
def print_linked_list(head):
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage
list1 = create_linked_list([1, 4, 5])
list2 = create_linked_list([1, 3, 4])
list3 = create_linked_list([2, 6])
lists = [list1, list2, list3]
merged = merge_k_lists(lists)
print("Merged list:")
print_linked_list(merged)
#include <stdio.h>
#include <stdlib.h>
// Definition for singly-linked list node
struct Node {
int data;
struct Node* next;
};
// Function prototype for merge_two_lists
struct Node* merge_two_lists(struct Node* l1, struct Node* l2);
// Function to merge k linked lists recursively
struct Node* merge_k_lists(struct Node** lists, int start, int end) {
// Base case: if the list is empty, return NULL
if (start > end) {
return NULL;
}
// Base case: if there's only one list, return it
if (start == end) {
return lists[start];
}
// Divide the lists into two halves
int mid = start + (end - start) / 2;
struct Node* left = merge_k_lists(lists, start, mid);
struct Node* right = merge_k_lists(lists, mid + 1, end);
// Merge the two halves
return merge_two_lists(left, right);
}
// Helper function to merge two linked lists
struct Node* merge_two_lists(struct Node* l1, struct Node* l2) {
// Base cases: if one list is empty, return the other
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
// Find tail node of list1 and connect it to head of list2
struct Node* current = l1;
while (current->next != NULL) {
current = current->next;
}
current->next = l2;
return l1;
}
// Helper function to create a linked list from an array
struct Node* create_linked_list(int arr[], int size) {
if (size == 0) {
return NULL;
}
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = arr[0];
head->next = NULL;
struct Node* current = head;
for (int i = 1; i < size; i++) {
current->next = (struct Node*)malloc(sizeof(struct Node));
current = current->next;
current->data = arr[i];
current->next = NULL;
}
return head;
}
// Helper function to print a linked list
void print_linked_list(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
// Example usage
int arr1[] = {1, 4, 5};
int arr2[] = {1, 3, 4};
int arr3[] = {2, 6};
// Create linked lists from arrays
struct Node* list1 = create_linked_list(arr1, sizeof(arr1) / sizeof(arr1[0]));
struct Node* list2 = create_linked_list(arr2, sizeof(arr2) / sizeof(arr2[0]));
struct Node* list3 = create_linked_list(arr3, sizeof(arr3) / sizeof(arr3[0]));
// Array of pointers to the linked lists
struct Node* lists[] = {list1, list2, list3};
int k = sizeof(lists) / sizeof(lists[0]);
// Merge the k linked lists
struct Node* merged = merge_k_lists(lists, 0, k - 1);
// Print the merged list
printf("Merged list:\n");
print_linked_list(merged);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
// Definition for singly-linked list node
class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Function prototype for merge_two_lists
Node* merge_two_lists(Node* l1, Node* l2);
// Function to merge k linked lists recursively
Node* merge_k_lists(vector<Node*>& lists) {
// Base case: if the list is empty, return nullptr
if (lists.empty()) {
return nullptr;
}
// Base case: if there's only one list, return it
if (lists.size() == 1) {
return lists[0];
}
// Divide the lists into two halves
int mid = lists.size() / 2;
vector<Node*> left(lists.begin(), lists.begin() + mid);
vector<Node*> right(lists.begin() + mid, lists.end());
// Recursively merge the left and right halves
Node* left_merged = merge_k_lists(left);
Node* right_merged = merge_k_lists(right);
// Merge the two halves
return merge_two_lists(left_merged, right_merged);
}
// Helper function to merge two linked lists
Node* merge_two_lists(Node* l1, Node* l2) {
// Base cases: if one list is empty, return the other
if (!l1) {
return l2;
}
if (!l2) {
return l1;
}
// Find tail node of list1 and connect it to head of list2
Node* current = l1;
while (current->next) {
current = current->next;
}
current->next = l2;
return l1;
}
// Helper function to create a linked list from a vector
Node* create_linked_list(const vector<int>& arr) {
if (arr.empty()) {
return nullptr;
}
Node* head = new Node(arr[0]);
Node* current = head;
for (size_t i = 1; i < arr.size(); i++) {
current->next = new Node(arr[i]);
current = current->next;
}
return head;
}
// Helper function to print a linked list
void print_linked_list(Node* head) {
Node* current = head;
while (current) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
// Helper function to free memory of a linked list
void free_linked_list(Node* head) {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
int main() {
// Example usage
vector<int> arr1 = {1, 4, 5};
vector<int> arr2 = {1, 3, 4};
vector<int> arr3 = {2, 6};
Node* list1 = create_linked_list(arr1);
Node* list2 = create_linked_list(arr2);
Node* list3 = create_linked_list(arr3);
vector<Node*> lists = {list1, list2, list3};
Node* merged = merge_k_lists(lists);
cout << "Merged list:" << endl;
print_linked_list(merged);
// Free memory
free_linked_list(merged);
return 0;
}
// Definition for singly-linked list node
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Function to merge k linked lists recursively
function mergeKLists(lists) {
// Base case: if the list is empty, return null
if (!lists || lists.length === 0) {
return null;
}
// Base case: if there's only one list, return it
if (lists.length === 1) {
return lists[0];
}
// Divide the lists into two halves
const mid = Math.floor(lists.length / 2);
const left = mergeKLists(lists.slice(0, mid));
const right = mergeKLists(lists.slice(mid));
// Merge the two halves
return mergeTwoLists(left, right);
}
// Helper function to merge two linked lists
function mergeTwoLists(l1, l2) {
// Base cases: if one list is empty, return the other
if (!l1) {
return l2;
}
if (!l2) {
return l1;
}
// Find tail node of list1 and connect it to head of list2
let current = l1;
while (current.next) {
current = current.next;
}
current.next = l2;
return l1;
}
// Helper function to create a linked list from a JavaScript array
function createLinkedList(arr) {
if (!arr || arr.length === 0) {
return null;
}
const head = new Node(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Helper function to print a linked list
function printLinkedList(head) {
let current = head;
let result = '';
while (current) {
result += current.data + ' -> ';
current = current.next;
}
result += 'null';
console.log(result);
}
// Example usage
const list1 = createLinkedList([1, 4, 5]);
const list2 = createLinkedList([1, 3, 4]);
const list3 = createLinkedList([2, 6]);
const lists = [list1, list2, list3];
const merged = mergeKLists(lists);
console.log("Merged list:");
printLinkedList(merged);
import java.util.ArrayList;
import java.util.List;
public class Main {
// Definition for singly-linked list node
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Function to merge k linked lists recursively
public static Node mergeKLists(List<Node> lists) {
// Base case: if the list is empty, return null
if (lists.isEmpty()) {
return null;
}
// Base case: if there's only one list, return it
if (lists.size() == 1) {
return lists.get(0);
}
// Divide the lists into two halves
int mid = lists.size() / 2;
List<Node> leftHalf = lists.subList(0, mid);
List<Node> rightHalf = lists.subList(mid, lists.size());
Node left = mergeKLists(leftHalf);
Node right = mergeKLists(rightHalf);
// Merge the two halves
return mergeTwoLists(left, right);
}
// Helper function to merge two linked lists
public static Node mergeTwoLists(Node l1, Node l2) {
// Base cases: if one list is empty, return the other
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
// Find tail node of list1 and connect it to head of list2
Node current = l1;
while (current.next != null) {
current = current.next;
}
current.next = l2;
return l1;
}
// Helper function to create a linked list from a Java array
public static Node createLinkedList(int[] arr) {
if (arr.length == 0) {
return null;
}
Node head = new Node(arr[0]);
Node current = head;
for (int i = 1; i < arr.length; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Helper function to print a linked list
public static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// Example usage
Node list1 = createLinkedList(new int[]{1, 4, 5});
Node list2 = createLinkedList(new int[]{1, 3, 4});
Node list3 = createLinkedList(new int[]{2, 6});
List<Node> lists = new ArrayList<>();
lists.add(list1);
lists.add(list2);
lists.add(list3);
Node merged = mergeKLists(lists);
System.out.println("Merged list:");
printLinkedList(merged);
}
}
Time and Space Complexity:
Time Complexity: O(n), where n is the total number of nodes.
Space Complexity: O(log k) due to the recursive call stack where k is the total number of lists.
Advantages and Disadvantages:
Advantages:
Elegant and concise implementation
Potential for parallelization/multithreading
Disadvantages:
Higher space complexity due to recursive calls
May cause stack overflow for very large number of lists
Similar Extensions of this Problem
Merge 2 Sorted Linked Lists: This problem involves combining two sorted linked lists into a single sorted linked list.
Merge K Sorted Lists: This problem involves merging K sorted linked lists into a single sorted linked list. It’s a more complex version of the basic merge problem as it requires maintaining sorted order during the merge.
Zip of Linked Lists: This involves interleaving nodes from multiple lists to create a single list. For example, given lists A->B->C and 1->2->3, the result would be A->1->B->2->C->3.
Merge with Deduplication: This extension involves merging multiple lists while removing duplicate elements, which adds an extra layer of complexity to the basic merging process.
Merge and Group: This involves merging multiple linked lists into multiple other linked lists based on certain rules, useful for grouping or categorizing data. For example, merging employee lists from different departments into lists based on job roles or salary ranges etc.