In this guide, we will explore the process of adjusting the partitioning of a provided singly linked list in C++ along with a detailed rationale and advantages.
Let's consider an input of a singly linked list. Our primary goal is to partition the list into two separate singly linked lists with distinct nodes from the original list. For instance, if the initial list comprises nodes labeled as a, b, c, d, e, and f, the resulting sub-lists will consist of nodes a, c, e and b, d, f following the division.
Afterward, we will select two indicators, N1 and N2, where one indicates the starting point of the initial list and the other also points to the start. Move both pointers to the next node to construct sub-lists.
Examples:
Input - List :- 1 → 5 → 7 → 12 → 2 → 96 → 33
Output - Original List: 1 5 7 12 2 96 33
List 1: 1 7 2 33
List 2: 5 12 96
Start from the first node and iterate through every fifth node in the linked list to create sublists as depicted above in the tutorial for the C++ programming language.
List: 13 → 53 → 90 → 18 → 44 → 11 → 99 → 32
Output - Original List: 13 53 90 18 44 11 99 32
List 1: 13 90 44 99
List 2: 53 18 11 32
Start from position 13 and 53 in the 'nexcpp' tutorial to form sublists by connecting alternate nodes as depicted above.
Simple Approach:
In this method, we'll use two pointers, N1 and N2 , one pointing to the original list's head and the other to the head of the following list. Shift both pointers to the subsequent node to build sublists.
- Consider the structure that has an int data component and a Node as the nexcpp tutorialer.
- Nodes are added to the head to construct a singly linked list using the function addtohead(Node** head, int data) .
- Create a singly linked list using the code mentioned earlier and a pointer to the first node as the head.
- The linked list is printed starting with the head node using the function display(Node* head) .
- Consider the Node1 and Node2 pointers.
- Node pointers are used in the splitList function, which points Node* head, Node n1 , and Node n2 to the head and next of the original string.
- Use split(n1, n2) inside it to divide the original list into two sublists.
- The split(Node N1, Node N2) function accepts two pointers, N1 and N2, and generates two sublists, each of which contains alternating nodes from the original list.
- Return nothing if N1 and N2 are both null.
- If N1's next is not null, set tmp=N1->next->next and set N1->next to the current time; if N2's next is not null, set tmp=N2->next->next and set N2->next to the current time; call split(N1->next, N2->next); for the following iteration.
- Print sublists using display function at the conclusion.
Program:
Let's consider a scenario to demonstrate how to modify the division of a provided singly linked list in C++.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addtohead(Node** head, int data){
Node* nodex = new Node;
nodex->data = data;
nodex->next = (*head);
(*head) = nodex;
}
void split(Node* N1, Node* N2){
Node *tmp;
if (N1 == NULL || N2 == NULL){
return;
}
if (N1->next != NULL){
tmp=N1->next->next;
N1->next = tmp;
}
if (N2->next != NULL){
tmp=N2->next->next;
N2->next = tmp;
}
split(N1->next, N2->next);
}
void splitList(Node* head, Node** n1, Node** n2){
*n1 = head;
*n2 = head->next;
split(*n1, *n2);
}
void display(Node* head){
Node* curr = head;
if (curr != NULL){
cout<<curr->data<<" ";
display(curr->next);
}
}
int main(){
Node* head = NULL;
Node *node1 = NULL, *node2 = NULL;
addtohead(&head, 20);
addtohead(&head, 12);
addtohead(&head, 15);
addtohead(&head, 8);
addtohead(&head, 10);
addtohead(&head, 4);
addtohead(&head, 5);
cout<<"Original List :"<<endl;
display(head);
splitList(head, &node1, &node2);
cout<<endl<<"List 1: ";
display(node1);
cout<<endl<<"List 2: ";
display(node2);
return 0;
}
Output:
Benefits of Alternating split of a given Singly Linked List
A single linked list is often split into two alternating portions by splitting it into two different lists, one of which contains nodes at even places and the other of which contains nodes at odd positions. We can achieve this by going through the first list several times and making two separate lists for odd and even spots. The advantages of splitting a single linked list in C++ alternately include the following:
- Better Data Organization: We can more logically arrange the data by dividing the list into two sublists . When working with items in a certain pattern or needing to conduct actions on odd and even elements individually, it can be quite helpful.
- Data Processing Simplified: Alternating split can make some data processing operations simpler. For instance, separating the list can make processing easier by isolating the alternating properties of the items (for example, students having roll numbers and names).
- Parallelism: Processing odd and even entries of a list in parallel may be desirable in some circumstances. In multi-core computers, splitting the list into odd and even portions can enhance speed by facilitating parallel processing.
- Algorithmic Practice: Dividing a linked list into alternating sections is a good practice for manipulating and traversing linked lists. The ability to work with linked data structures will improve as a result.
- Modular Code: Create functions or methods to carry out the alternating split to increase the modularity and maintainability of our code. This separation of concerns can enhance the readability and reuse of code.
- Enhanced Testing: Dividing the list into two sections makes it simpler to test and troubleshoot particular activities on each portion. We can concentrate on testing the reasoning behind even-positioned nodes apart from the reasoning behind odd-positioned nodes.
- Flexibility: Flexibility in data handling and manipulation is made possible by the capability to divide a singly linked list into alternating sections. We can modify the code to comply with different data patterns and specifications.
