Trusted answers to developer questions
Split a linked list into two sublists with alternating elements
Chayshta SinghOverview
The following article will go through how to split a linked list into two sub-lists with each containing alternate elements from the original list.
Algorithm
Append the current element to one of the two sub-lists while traversing the original list, list 1. We will use a boolean variable to determine whether the entry is added to list 2 or list 3. This variable value toggles between true and false with each iteration.
The following are the two points to be considered in the solution:
- Function signature: Use reference to a pointer.
- Fix the tail of list 2 and list 3 to point to
nullptr.
Code
Node.h
#include<iostream>
#include "Node.h"
using namespace std;
// head is a pointer to original list
// head1 is a reference to a pointer to sublist 1
// head2 is a reference to a pointer to sublist 2
void split(Node *head, Node *&head1, Node *&head2){
Node *current1 = nullptr, *current2 = nullptr;
Node *current = head;
bool alternate = true;
while(current){
if(alternate){
// add element in list1 for alternate = true
if(current1){
current1->next = current;
current1 = current1->next;
}
else
current1 = head1 = current;
} else {
// add element in list2 for alternate = false
if(current2){
current2->next = current;
current2 = current2->next;
}
else
current2 = head2 = current;
}
current = current->next;
alternate = !alternate;
}
//fix the tail pointers of list1 and list2
if(current1)
current1->next = nullptr;
if(current2)
current2->next = nullptr;
}
//list1 will contain these values.
int arr[] = {1,2,3,4,5,6,7,8,9};
int size = 9;
Code
Time complexity analysis
The algorithm's time complexity is O(N), where N is the length of the original linked list.
Explanation
- Lines 16–22: This section works only for
truevalues of thealternatevariable. Data of thecurrentpointer is appended tocurrent1. Thehead1keyword is initialized if it’s the first element in the list. - Lines 24–29: This section work only for
falsevalues of thealternatevariable. Data of thecurrentpointer is appended tolist2. Then, thehead2keyword is initialized if it’s the first element in the list. - Line 36: If
current1is not the first entry in thelist1, we will set its next value tonullptrafter appending. - Line 38: If
current2is not the first entry in thelist2, we will set its next value tonullptrafter appending.
RELATED TAGS
c++
linked list
CONTRIBUTOR
Chayshta SinghRELATED COURSES
View all Courses
Keep Exploring
Related Courses
