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>?.