Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
linked list

Split a linked list into two sublists with alternating elements

Chayshta Singh

Overview

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:

  1. Function signature: Use reference to a pointer.
  2. 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 true values of the alternate variable. Data of the current pointer is appended to current1. The head1 keyword is initialized if it’s the first element in the list.
  • Lines 24–29: This section work only for false values of the alternate variable. Data of the current pointer is appended to list2. Then, the head2 keyword is initialized if it’s the first element in the list.
  • Line 36: If current1 is not the first entry in the list1, we will set its next value to nullptr after appending.
  • Line 38: If current2 is not the first entry in the list2, we will set its next value to nullptr after appending.

RELATED TAGS

c++
linked list
RELATED COURSES

View all Courses

Keep Exploring