Problem name: Merging and Sorting Multiple Linked Lists
Topic Tags: Sorting, Merging, Linked Lists
Level: Medium
Language used: C++
Problem Statement:
You have multiple linked lists represented by strings. Each string is composed of uppercase
and/or lowercase letters, which represent the values of nodes in the linked list. Your task is to:
Sort each linked list in ascending order of characters.
Merge all the sorted linked lists into a single sorted linked list.
Note:
If any input string contains non-alphabetic characters, return -1 immediately.
Mixed case strings should be considered invalid (e.g., "Abc" should return -1).
Input Format:
The first line contains an integer N indicating the number of linked lists.
The next N lines each contain a string representing the values for each linked list.
Output Format:
Print the final sorted merged linked list as a single string. If any input string is invalid, print -1.
Constraints:
1 <= N <= 1000
A <= String <= Z
a <= String <= z
Sample Input 1:
3
abc
def
ghi
Sample Output 1:
abcdefghi
Explanation for Sample case 1:
Each linked list represented by the strings "abc", "def", and "ghi" is already sorted. When
merged, the final linked list is "abcdefghi".
Sample Input 2:
4
abc
zyx
mno
def
Sample Output 2:
abcdefmnoxyz
Explanation for Sample case 2:
4 // number of linked list
abc // already sorted
zyx // sorts to xyz
mno //already sorted
def //already sorted
The linked lists are sorted alphabetically. After merging, the final linked list is "abcdefmnoxyz".
Sample Code:
#include <iostream>
#include <vector>
#include <cctype>
using namespace std;
class Node {
public:
char value;
Node* next;
Node(char value) {
this->value = value;
next = nullptr;
}
};
class LinkedList {
private:
Node* head;
Node* tail;
int length;
Node* mergeSort(Node* head) {
if (!head || !head->next) return head;
Node* mid = getMiddle(head);
Node* left = head;
Node* right = mid->next;
mid->next = nullptr;
return merge(mergeSort(left), mergeSort(right));
}
Node* getMiddle(Node* head) {
if (!head) return head;
Node* slow = head;
Node* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
Node* merge(Node* left, Node* right) {
Node dummy(0);
Node* tail = &dummy;
while (left && right) {
if (tolower(left->value) < tolower(right->value)) {
tail->next = left;
left = left->next;
} else {
tail->next = right;
right = right->next;
}
tail = tail->next;
}
tail->next = left ? left : right;
return [Link];
}
public:
LinkedList() {
head = nullptr;
tail = nullptr;
length = 0;
}
~LinkedList() {
Node* temp;
while (head) {
temp = head;
head = head->next;
delete temp;
}
}
void printList() const {
Node* temp = head;
if (temp == nullptr) {
cout << "empty";
} else {
while (temp != nullptr) {
cout << temp->value;
temp = temp->next;
}
}
cout << endl;
}
Node* getHead() const {
return head;
}
int getLength() const {
return length;
}
void append(char value) {
Node* newNode = new Node(value);
if (length == 0) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
length++;
}
void sort() {
head = mergeSort(head);
Node* temp = head;
while (temp && temp->next) {
temp = temp->next;
}
tail = temp;
}
void merge(LinkedList& otherList) {
if (![Link]()) return;
head = merge(head, [Link]());
Node* temp = head;
while (temp && temp->next) {
temp = temp->next;
}
tail = temp;
length += [Link]();
[Link] = nullptr;
[Link] = nullptr;
[Link] = 0;
}
};
bool isValidInput(const string& s) {
bool hasLower = false, hasUpper = false;
for (char c : s) {
if (!isalpha(c)) {
return false;
}
if (islower(c)) hasLower = true;
if (isupper(c)) hasUpper = true;
}
return !(hasLower && hasUpper);
}
int main() {
int N;
cin >> N;
vector<string> inputs(N);
for (int i = 0; i < N; i++) {
cin >> inputs[i];
}
for (const string& s : inputs) {
if (!isValidInput(s)) {
cout << -1 << endl;
return 0;
}
}
vector<LinkedList> lists(N);
for (int i = 0; i < N; i++) {
for (char c : inputs[i]) {
lists[i].append(c);
}
lists[i].sort();
}
LinkedList mergedList;
for (int i = 0; i < N; i++) {
[Link](lists[i]);
}
[Link]();
return 0;
}
OneCompiler Link:
Merging and Sorting Multiple Linked Lists