Rearrange a linked list such that all even and odd positioned nodes are together

Ishita Chawla
Last Updated: May 13, 2022

Introduction

linked list is a linear data structure where elements are not stored contiguously but randomly. They are instrumental in implementing stacks and queuesgraphs, performing arithmetic operations on large integers, and representing sparse matrices. 

It is a vital topic from the placement point of view, and there are several problems related to it.

This blog will discuss one such significant problem, to rearrange a linked list such that all even and odd positioned nodes are together.

Problem Statement

You have been provided with the head pointer of a singly linked list. Your task is to rearrange the elements of the linked list such that all the nodes at the even positions occur together and all the nodes at the odd positions occur together. Let us look at a few examples to get a clear understanding.

Example:

  •       Input:    1→2→3→4→5

Output:  1→3→5→2→4

  •       Input:     2→1→3→5→6→4→7 

Output:   2→3→6→7→1→5→4

Algorithm

Before solving the problem, one thing that should be kept in mind is the different cases possible in the linked list:

  • No nodes
  • One node
  • Two nodes
  • Odd number of nodes
  • Even number of nodes


So, keeping in mind all the above cases, we can design the following algorithm:

  • Maintain 2 pointers ‘ODD’ and ‘EVEN’ for the node at the odd and even positions, respectively.
  • Traverse the original linked list and put the odd nodes in the odd linked list and the even nodes in the even linked list.
  • Also, store the first node of the even linked list so that the even linked list can be attached at the end of the odd list after all the odd and even nodes have been connected in different lists.


INITIAL STEP:
 


STEP 1:


STEP 2:


STEP 3:

Implementation

Program

// C++ program to rearrange a linked list such that all even and odd positioned nodes are together.
#include <iostream>
using namespace std;

// 'NODE' class to store linked list nodes.
class Node
{
    public:
    int data;
    Node *next;

    // Constructor to create a node with given data.
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};

// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{

    // 'HEAD' pointer to store the address of the first node.
    Node *head;
   
    public:
    LinkedList()
    {
        head = NULL;
    }

    // Function to print the linked list elements.
    void printLinkedList()
    {

        /*
            'CURRENT' node pointer traverses through the linked list.
            Set 'CURRENT' node equal to the first node of the linked list.
        */
        Node *current = head;

        // Loop to traverse the linked list.
        while (current)
        {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    // Function to insert nodes in the linked list.
    void insert(int data)
    {

        /*  If linked list is empty, create a new node
            and direct the 'HEAD' node to the newly created node.
        */
        if (head == NULL)
        {
            head = new Node(data);
            return;
        }

        // Else traverse the linked list until the end of the list is encountered.
        Node *current = head;
        while (current->next)
        {
            current = current->next;
        }

        // Create and insert a new node at the end of the linked list.
        current->next = new Node(data);
    }

    // Function to rearrange a linked list such that all even and odd positioned nodes are together.
    void rearrangeEvenOdd()
    {
        if (head == NULL)
            return;

        // Initialising the first nodes of even and odd lists.
        Node *odd = head;
        Node *even = head->next;

        // Storing the first node of the linked list so that it can be connected at the end of the odd list.
        Node *evenFirst = even;

        while (1)
        {
            // If the odd list and the even lists have ended, the first node of the even linked list is connected to the last node of the odd linked list.
            if (!odd || !even || !(even->next))
            {
                odd->next = evenFirst;
                break;
            }

            // Connecting the odd nodes.
            odd->next = even->next;
            odd = even->next;

            // If there are no more even nodes after the current odd node.
            if (odd->next == NULL)
            {
                even->next = NULL;
                odd->next = evenFirst;
                break;
            }

            // Connecting the even nodes.
            even->next = odd->next;
            even = odd->next;
        }
    }
};

int main()
{
    int n;

    // Taking user input.
    cout << "Enter the size of the linked list: ";
    cin >> n;

    cout << "Enter the values of the nodes: ";
    LinkedList *givenList = new LinkedList();
    for (int i = 0; i < n; i++)
    {
        int data;
        cin >> data;
        givenList->insert(data);
    }

    // Calling the function to rearrange the linked list such that all even and odd positioned nodes are together.
    givenList->rearrangeEvenOdd();

    // Printing this modified linked list.
    cout << "The modified linked list is: ";
    givenList->printLinkedList();

    return 0;
}

Input

Enter the size of the linked list: 5
Enter the values of the nodes: 
1 2 3 4 5 

Output

The modified linked list is:
1 3 5 2 4

Time Complexity

O(N), where N is the size of the linked list.

Since we are traversing the entire linked list with N nodes only once, the time complexity is given by O(N).

Space Complexity

The space complexity is O(1).

The space complexity is constant as we are not using extra space except variables and pointers.

Key Takeaways

So, this blog discussed how to rearrange a linked list such that all even and odd positioned nodes are together. To learn more, head over right now to CodeStudio to practice problems on topics like Linked ListGraphsTrees and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think