Put elements at Even position after elements at Odd position in a Linked List

Question

The question is asking us to put elements at odd positions before elements at even position in a linked list.

Test Cases:

{1, 2, 3, 4, 5, 6} --> {1, 3, 5, 2, 4, 6}

{1, 2, 3, 4, 5, 6, 7} --> {1, 3, 5, 7, 2, 4, 6}

My Code:

#include <bits/stdc++.h>
using namespace std;

class node
{
public:
    int data;
    node *next;

    node(int value)
    {
        data = value;
        next = NULL;
    }
};

void InsertAtHead(node *&head, int val)
{
    node *n = new node(val);

    n->next = head;
    head = n;
}

void InsertAtTail(node *&head, int val)
{
    if (head == NULL)
    {
        InsertAtHead(head, val);
        return;
    }
    node *n = new node(val);

    node *temp = head;

    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = n;
}

void EvenOdd(node *&head)
{
    node *odd = head;
    node *even = head->next;
    node *evenStart = even;

    while (odd->next != NULL && even->next != NULL)
    {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }
    if (odd->next == NULL)
    {
        even->next = NULL;
    }
    odd->next = evenStart;
}

void display(node *head)
{
    node *temp = head;

    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main()
{
    node *head = NULL;

    int a[] = {1, 2, 3, 4, 5, 6, 7};

    for (int i = 0; i < 7; i++)
    {
        InsertAtTail(head, a[i]);
    }
    display(head);

    EvenOdd(head);
    display(head);

    return 0;
}

This code will only work for even number of nodes in Linked List. If we take odd number of nodes in a Linked List, then it will show segmentation fault.

For example: This code will work correctly for 1st test case.

But for second test case, it will show segmentation fault.

Answer 1

Before you go into loop in OddEven, odd is 1 and even is 2.

    while (odd->next != NULL && even->next != NULL)
    {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }

After first loop, odd is 3 and even is 4. Next is odd is 5 and even is 6, then odd is 7 and even is NULL.

    if (odd->next == NULL)
    {
        even->next = NULL;
    }

Since even is NULL, even->next becomes a problem and throw segmentation fault. You can just remove that part as whole.

Not related but take a look at Why should I not #include <bits/stdc++.h>?.

Answer 2

This looks like a homework problem so I do not want to give the exact answer. You are heading in the correct direction in your EvenOdd() function with:

node *odd = head;
node *even = head->next;
node *evenStart = even;

However, start with:

node *odd = nullptr;
node *even = nullptr;
node *current = head;

while (current != nullptr)
{
    // partition into odd and even sets here

    current = current->next;
}

// put the first even-node pointer at the end of the odd partition

It might be a big learning curve but put your code at the top of a Visual Studio test library class or rewrite the source file as a Googletest file. That way, you can execute both test patterns you identified in your question. Also:

1. What happens if the list contains an odd number of items?
2. What if it is an empty list?

From there, you can easily add more test cases and re-test your code.

Answer 3

My five cents.:)

For starters there is no any need to declare explicitly a constructor for the class node.

class node
{
public:
    int data;
    node *next;

    node(int value)
    {
        data = value;
        next = NULL;
    }
};

Your life will be simpler if you will deal with an aggregate. For example

struct node
{
    int data;
    node *next;
};

The function name EvenOdd is confusing because as it follows from your examples you want rearrange the list such a way that nodes at odd positions would precede nodes at even positions and you are counting positions starting from 1. So the function name should be at least OddEven. Otherwise if to start positions from 0 then the function name indeed should be EvenOdd.

The function initially can invoke undefined behavior because there is no check whether head is equal to nullptr. So there can be used a null pointer to access a memory for example in these statements

node *even = head->next;

and

while (odd->next != NULL && even->next != NULL)

Moreover it is not necessary that the list contains a sequence of nodes where nodes with odd values and even values alternate. For example try to run your function for a list that contains the following sequence of numbers { 1, 3, 2, 4, 5 }.

I would write the program the following way

#include <iostream>
#include <functional>
#include <iterator>

struct node
{
    int data;
    node *next;
};

void push_front( node * &head, int data  )
{
    head = new node { data, head };
}

void clear( node * &head )
{
    while ( head ) delete std::exchange( head, head->next );
}

std::ostream & display( node * &head, std::ostream &os = std::cout )
{
    for ( const node *current = head; current; current = current->next )
    {
        os << current->data << ' ';
    }
    
    return os;
}

template <typename InputIterator>
void create( node * &head, InputIterator first, InputIterator last )
{
    clear( head );
    
    node **current = &head;
    
    for ( ; first != last; ++first )
    {
        *current = new node { *first, nullptr };
        current = &( *current )->next;
    }
}

node * EvenOdd( node * &head )
{
    node **odd = &head;
    node *even_head = nullptr;
    node **even = &even_head;
    
    size_t pos = 0;
    
    while ( *odd )
    {
        if ( pos++ % 2 != 0 )
        {
            *even = *odd;
            *odd = ( *odd )->next;
            ( *even )->next = nullptr;
            even = &( *even )->next;
        }
        else
        {
            odd = &( *odd )->next;
        }
    }
    
    *odd = even_head;
    
    return even_head;
}

int main() 
{
    node *head = nullptr;
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    create( head, std::begin( a ), std::end( a ) );
    
    display( head ) << '\n';
    
    auto pos = EvenOdd( head );
    
    display( head ) << '\n';
    display( pos ) << '\n';
    
    clear( head );
    
    return 0;
}

The program output is

0 1 2 3 4 5 6 7 8 9 
0 2 4 6 8 1 3 5 7 9 
1 3 5 7 9 

Answer 4

This doesn't answer your question in so far as it doesn't explain what is wrong with your attempt. If anyone answers that, then that'll be a better answer.

However this answer is more for your information how it'd be solved using the standard C++ library algorithms, which is available to you and there's no shame in using.

#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7};

    // a lambda function that tests whether a single number is odd
    auto is_odd = [](int i){ return i % 2 > 0; };

    // reorganise elements such that odd numbers are moved to the front, maintaining their original order (stable)
    std::stable_partition(v.begin(), v.end(), is_odd);

    // output elements (space delimited) to console 
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Answer 5

When the number of elements in the lists is odd, the even pointer is pointing to NULL, making it impossible to access the next node of even during the while condition. Try the following code and it will solve your issue.

#include<bits/stdc++.h>
using namespace std;

class node{
    public:
    int data;
    node* next;

    node(int val){
        data = val;
        next = NULL;
    }
};

void insertAtTail(node* &head,int val){
    node* n = new node(val);

    if(head == NULL){
        head = n;
        return;
    }

    node* temp = head;
    while(temp->next!=NULL){
        temp=temp->next;
    }

    temp->next = n;

    return;
}

void display(node* &head){
    node* temp = head;
    while(temp!=NULL){
        cout<<temp->data;
        if(temp->next!=NULL){
            cout<<"->";
        }
        temp = temp->next;
    }

    cout<<endl;

    return;
}

void evenAfterOdd(node* &head){
    node* odd = head;
    node* even = head->next;
    node* evenStart = even;

    while(odd->next!=NULL && even->next!=NULL){
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        if(even->next!=NULL){
            even = even->next;
        }else{
            break;
        }
    }

    odd->next = evenStart;

    return;
}

int main(){
    node* head = NULL;
    int arr[] = {1,2,3,4,5,6,7};
    for(int i=0;i<6;i++){
        insertAtTail(head,arr[i]);
    }

    display(head);

    evenAfterOdd(head);
    display(head);



    return 0;
}

Hope you find it helpful! :)

Answer 6

Not answering your question, but suggesting an easier way to solve the problem.

You can also loop backwards over the linked list and move all odd numbers to the start of the list.

It would look something like this:

int main()
{
    node *head = NULL;

    int a[] = {1, 2, 3, 4, 5, 6, 7};

    for (int i = 7; i > 0; i--)
    {
        if(value == odd) {
            move to front of the list
    }

    return 0;
}