Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Algorithm
2.2.
Implementation
2.3.
Complexity Analysis
3.
Frequently Asked Questions(FAQs)
3.1.
What is a linked list?
3.2.
What is the key difference between a singly linked list and a doubly-linked list?
4.
Conclusion
Last Updated: Mar 27, 2024

Rearrange a Linked List such that all Even and Odd Positioned Nodes are Together

Author Ishita Chawla
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Linked List

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, rearranging a linked list such that all even and oddly positioned nodes are together.

Also see Data Structures

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 the 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:
 

illustration image

STEP 1:

illustration image

STEP 2:

illustration image

STEP 3:

illustration image

Implementation

// 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;
}

You can also try this code with Online C++ Compiler
Run Code

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

Complexity Analysis

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 for variables and pointers.

Recommended Topic, Floyds Algorithm

Frequently Asked Questions(FAQs)

What is a linked list?

A linked list is a linear data structure that is formed by connected nodes. Each node has a value associated with it and the pointer(s) to its directly connected node(s).   

What is the key difference between a singly linked list and a doubly-linked list?

A singly-linked list is unidirectional, which means that the node of a singly-linked list contains the pointer to its next node only. In contrast, a doubly-linked list is bidirectional, and its node contains the pointer to its next and previous nodes.

Conclusion

So, this blog discussed how to rearrange a linked list such that all even and oddly positioned nodes are together. To learn more, head over right now to Coding Ninjas Studio to practice problems on topics like Linked ListGraphs, and Trees, 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.

Recommended Reading:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass