Linked lists are a fundamental data structure in the field of computer science and are commonly encountered in various computer systems and programming languages. Unlike arrays, linked lists are dynamic and utilize memory efficiently by linking individual nodes sequentially through pointers to form a sequence. One common challenge associated with linked lists is modifying the position of elements while maintaining a specific order or structure.
In this article, we are going to explore a traditional issue related to linked lists: Moving all occurrences of a specific element in a linked list to the end of the list. This particular problem is frequently used to demonstrate various aspects of linked list manipulation, including maintaining element order and analyzing time complexity.
Suppose you possess a linked list containing multiple occurrences of a specific value that you aim to sort in ascending order while retaining the original order of all other elements. Additionally, for duplicate instances of the target value, their relative positions must remain unchanged. This distinction sets this task apart from a standard reordering of nodes within the linked list.
To make this concept more concrete, let's illustrate with an instance. Imagine you have a linked list:
Input: 1 -> 2 -> 2 -> 3 -> 4 -> 2 -> 5
Target: 2
Output: 1 -> 3 -> 4 -> 5 -> 2 -> 2 -> 2
The sequence commences with a diverse range of items; indeed, there are multiple twos present in the sequence. Following the process, all instances of the number 2 are rearranged immediately prior to the final element of the sequence, with the rest of the elements unaffected and retaining their original order of 1, 3, 4, 5. The twos that were relocated also maintain their original sequence.
This challenge is well-known in competitive programming and technical interviews as it evaluates the coder's grasp of handling linked lists efficiently and accurately, often requiring quick and precise solutions. This proficiency is valuable not only in theoretical scenarios but also in practical settings where related data manipulation is common, like organizing tasks or restructuring dynamic data structures.
Problem Statement
The task can be formally described as follows:
Rearrange the elements of a singly linked list by moving a specified value x to the end of the list without changing the positions of other elements or altering the positions of target values.
For example:
Input: 1 -> 4 -> 5 -> 4 -> 3, Target: 4 Output: 1 -> 5 -> 3 -> 4 -> 4
Input: 7 -> 7 -> 8 -> 7, Target: 7 Destination: 8 -> 7 -> 7 -> 7
Input: state 9 -> 1 -> 9 -> 2 -> 9 Target: 3 -> Output: 9 -> 1 -> 9 -> 2 -> 9 No transition because the target does not exist.
To accomplish this task, we need to effectively address several important obstacles related to linked list manipulation:
In pointer manipulation, a linked list distinguishes itself from an array by lacking a direct index pointer. To access data elements, one needs to navigate the linked list using pointers. Since these pointers are the sole means provided to rearrange the nodes, it is crucial to manage them properly to prevent data loss or potential list corruption.
Order Maintenance: Hence, preserving the sequence of non-targets and targets adds an additional challenge. For instance, in the result, 1 -> 3 -> 4 -> 4; In the initial sequence, it should be 1 -> 4 -> 4 -> 3. It's crucial not to swap 1 and 3. Likewise, the duplicates 4 and 4 remain in their original positions.
Efficiency: An alternative straightforward approach involves utilizing a secondary list or looping back over the original list to rearrange desired elements. However, this method could lead to suboptimal performance when dealing with extensive lists, making it less than optimal for such scenarios. The optimal approach would involve traversing the list only once or, in the most efficient scenario, a maximum of two times.
Key Challenges
Swapping elements within a linked list or any data structure using pointers can be quite complex, especially when attempting to update all instances of a specific value. The difficulties primarily stem from the unique characteristics of linked lists, where node pointers are utilized for manipulating nodes instead of direct indexing like in arrays.
1. Pointer Management
The linked list does not allow for direct element access; instead, it navigates nodes through pointers. When rearranging elements, it's essential to update the node pointers to maintain list integrity. Pointer errors can lead to broken links, circular references, or data loss, imposing critical constraints on data views.
For instance, if a node needs to be relocated to the end of the list, the process involves removing the node, updating the pointer of the preceding node, and designating the node as the new tail. The challenge in handling these modifications lies in the fact that any alteration at one level could impact other elements within the list.
2. Order Preservation
Maintaining the original sequence of non-target and target nodes adds complexity to the task. For example, in a sequence like 1 -> 2 -> 3 -> 2 -> 4 -> 2, the resulting sequence must retain the order of non-target nodes (1, 3, 4) in relation to the target nodes (2, 2, 2). This restriction rules out straightforward solutions, like grouping nodes independently of their flow.
3. Efficiency
If the algorithm lacks efficiency, such as needing a single pass through a list to locate and move the desired nodes, it results in a time complexity of O(n^2). This process of searching becomes costly for larger linked lists in terms of computation. The effectiveness of the solution necessitates traversing the list in O(n) time, impacting each node just once.
4. Edge Cases
Some scenarios to address include an empty list, a list with only one node, or a list containing all or none of the target values. These particular cases provide valuable insights to assess the solution thoroughly and determine its relevance and effectiveness.
Code:
#include <iostream>
using namespace std;
// Definition of a linked list node
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Function to move all occurrences of 'target' to the end of the linked list
Node* moveOccurrencesToEnd(Node* head, int target) {
if (!head) return head;
// Dummy nodes for two partitions: one for non-target and one for target
Node *nonTargetDummy = new Node(0), *targetDummy = new Node(0);
Node *nonTargetTail = nonTargetDummy, *targetTail = targetDummy;
Node* current = head;
// Traverse the list and partition nodes
while (current) {
if (current->data == target) {
targetTail->next = current;
targetTail = targetTail->next;
} else {
nonTargetTail->next = current;
nonTargetTail = nonTargetTail->next;
}
current = current->next;
}
// Combine the two partitions
nonTargetTail->next = targetDummy->next;
targetTail->next = nullptr;
Node* newHead = nonTargetDummy->next;
// Free the dummy nodes
delete nonTargetDummy;
delete targetDummy;
return newHead;
}
// Helper function to add a node to the end of the list
Node* addNode(Node* head, int data) {
if (!head) return new Node(data);
Node* current = head;
while (current->next) current = current->next;
current->next = new Node(data);
return head;
}
// Helper function to print the linked list
void printList(Node* head) {
while (head) {
cout << head->data << " -> ";
head = head->next;
}
cout << "nullptr\n";
}
// Helper function to free the linked list memory
void freeList(Node* head) {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
// Main function to test the program
int main() {
Node* head = nullptr;
// Create a linked list: 1 -> 2 -> 2 -> 3 -> 4 -> 2 -> 5
head = addNode(head, 1);
head = addNode(head, 2);
head = addNode(head, 2);
head = addNode(head, 3);
head = addNode(head, 4);
head = addNode(head, 2);
head = addNode(head, 5);
cout << "Original List:\n";
printList(head);
int target = 2;
// Move all occurrences of the target to the end
head = moveOccurrencesToEnd(head, target);
cout << "\nList After Moving Target (" << target << ") to the End:\n";
printList(head);
// Free allocated memory
freeList(head);
return 0;
}
Input:
Original list:
1 -> 2 -> 2 -> 3 -> 4 -> 2 -> 5 -> nullptr
Target: 2
Output:
List after moving all occurrences of the target (2) to the end:
1 -> 3 -> 4 -> 5 -> 2 -> 2 -> 2 -> nullptr
