Understanding
This blog discusses a problem based on linked lists. Linked lists are among the most important and popular data structures asked in programming contests and technical interviews. There are several standard problems and operations based on linked lists. This blog takes a coding challenge that covers two such standard operations: merging two linked lists and reversing a linked list without using extra space.
Problem Statement
Ninja has given you a non-decreasing linked list. Your task is to square the linked list elements and sort them without using any extra space. You should return the same linked list but its elements squared and sorted.
Input
Linked list: (-3)->(-1)->0->1->2
Output
Output Linked list: 0->1->1->4->9
Explanation
Linked list with elements squared: 9->1->0->1->4
Sort the linked list: 0->1->1->4->9
Approach
We can solve this problem by taking hints from two standard operations on linked lists, namely:
- Reverse a linked list without using extra space
- Merge two linked lists without using extra space
In this problem, we can split the linked list into two parts: L1 and L2.
L1 contains all nodes from the given linked list with negative elements, while L2 contains the rest of the linked list. Now, we can follow the below-mentioned procedure to get the desired linked list:
- Square the elements of L1 and L2.
- Reverse L1 without using any extra space.
- Merge L1 and L2 using the standard merge procedure.
As you can see, after step 2, the elements of both L1 and L2 are sorted, and hence the merge procedure will output the desired sorted linked list.
Algorithm
- Create the input linked list.
- Iterate on the linked list and split it at the first node with a non-negative value. Let L1 be the linked list with all negative nodes and L2 be the remaining linked list.
- Square the elements of L1 and L2.
- Reverse L1 using the standard reverse linked list implementation. You can read more about implementation here.
- Merge L1 and L2. You can read more about implementation here.
- Print the merged linked list using the standard merge procedure.
Program
#include<iostream>
#include<vector>
using namespace std;
// Node structure in a linked list.
class Node
{
public:
// Element value in a node and next pointer.
int val;
Node* next;
// Constructor to create a node.
Node(int val)
{
this->val = val;
this->next = NULL;
}
};
// Function to split a linked list into two linked lists as explained in the approach.
Node* splitList(Node* head)
{
// Initialize the positiveLL pointer with NULL.
Node* positiveLL = NULL;
while(head!=NULL && head->next!=NULL){
// If the next pointer of the current node is non-negative, split the linked list here.
if(head->next->val>=0)
{
// Update the positiveLL pointer if the above condition is true and break.
positiveLL = head->next;
head->next = NULL;
break;
}
// Keep going ahead until a node satisfies the desired condition.
head = head->next;
}
// return the first node with a non-negative value as the head of the positive linked list.
return positiveLL;
}
// Print the linked list.
void printLL(Node* head)
{
while(head)
{
cout<<head->val;
if(head->next != NULL){
cout<<" -> ";
}
head = head->next;
}
cout<<endl;
}
// Utility function to square the elements of a linked list.
void squareLL(Node* head)
{
Node* dummyhead = head;
while(dummyhead)
{
dummyhead->val = dummyhead->val * dummyhead->val;
dummyhead = dummyhead->next;
}
}
// Utility function to reverse a linked list.
Node* reverseLL(Node* head)
{
// Standard Implementation.
// Initialize three pointers temp, curr and prev as follows.
Node* prev = NULL;
Node* temp = NULL;
Node* curr = head;
// While the curr pointer is not null, do this.
while(curr != NULL)
{
// Store the next pointer of curr node.
temp = curr->next;
// Reverse the next pointer of curr node to pointer to prev node.
curr->next = prev;
// Update prev and curr as you move forward in the linked list.
prev = curr;
curr = temp;
}
// Return the new head.
return prev;
}
// Merge two linked lists.
Node* mergeLL(Node* L1, Node* L2)
{
// Case when one of the linked list is empty.
if(L1 == NULL || L2 == NULL)
{
if(L1 == NULL) return L2;
return L1;
}
// Pointer to the merged linked list.
Node* sortedPointer = NULL;
Node* dummyAns = NULL;
while(L1 != NULL && L2 != NULL)
{
// Take the node with smaller element.
if(L1->val < L2->val)
{
// If this is the first node in the merged linked list.
if(sortedPointer == NULL)
{
sortedPointer = L1;
dummyAns = sortedPointer;
}
else
{
// Make the necessary pointer adjustments.
sortedPointer->next = L1;
sortedPointer = sortedPointer->next;
}
// Move the pointer forward.
L1 = L1->next;
}
else
{
// Similar to the first case.
if(sortedPointer == NULL)
{
sortedPointer = L2;
dummyAns = sortedPointer;
}
else
{
sortedPointer->next = L2;
sortedPointer = sortedPointer->next;
}
L2 = L2->next;
}
}
// Join any remaining linked list.
if(L1 != NULL) sortedPointer->next = L1;
else if(L2 != NULL) sortedPointer->next = L2;
return dummyAns;
}
Node* solve(Node* head)
{
// Case when the linked list contains only non-negative elements.
if(head->val >= 0)
{
// No need to merge as even after squaring, the elements will be sorted.
// Simply square the elements and print the linked list.
squareLL(head);
return head;
}
Node* positiveLL = splitList(head);
// Square the elements of the linked lists.
squareLL(head);
squareLL(positiveLL);
// Reverse the linked list with initially negative elements to make it sorted.
Node* negativeLL = reverseLL(head);
// Merge the linked lists now.
Node* sortedPointer = mergeLL(positiveLL, negativeLL);
return sortedPointer;
}
int main()
{
// Number of nodes in the linked list.
int n;
cin>>n;
// Elements in the linked list.
vector<int> arr(n);
for(int i = 0; i < n; i++){
cin>>arr[i];
}
// Create the linked list.
Node* head = new Node(arr[0]);
Node* dummyhead = head;
for(int i = 1; i < n; i++)
{
Node* newnode = new Node(arr[i]);
dummyhead->next = newnode;
dummyhead = newnode;
}
Node* sortedPointer = solve(head);
printLL(sortedPointer);
}
Input
5
-3 -1 0 1 4
Output
0->1->1->4->9
Time Complexity
The time complexity of the above approach is O(N), where N is the number of nodes in the linked list.
It is because the time complexity of both merge and reverse procedures is O(N).
Space Complexity
The space complexity of the above approach is O(1)
As we are using constant memory space.
Key Takeaways
In this blog, we learned about two standard operations on linked lists: merging two linked lists and reversing a linked list, both without using extra space. We discussed a problem that involves the usage of these procedures serially to achieve the result. There are several other problems based on linked lists, like detecting a loop in a linked list, etc.
Hence learning never stops. So head over to our coding platform CodeStudio to practice problems based on data structures and algorithms.
Recommended Problems -