1.Odd-Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Here the odd-even refers to node number and not the value in the nodes.

Description:

// Example input output
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Solution I : (Using two traversal and new list)

class Solution
{
public:
    ListNode *oddEvenList(ListNode *head)
    {

        ListNode *head1 = NULL;
        if (head == NULL)
        {
            return head;
        }

        ListNode *p = head;
        int i = 1;
        while (p != NULL)
        {
            if (i % 2 != 0)
            {
                ListNode *temp = new ListNode;
                temp->val = p->val;
                temp->next = NULL;
                if (head1 == NULL)
                {
                    head1 = temp;
                }
                else
                {
                    ListNode *q = head1;
                    while (q->next != NULL)
                    {
                        q = q->next;
                    }
                    q->next = temp;
                }
            }
            p = p->next;
            i++;
        }

        i = 1;
        p = head;
        while (p != NULL)
        {
            if (i % 2 == 0)
            {
                ListNode *temp = new ListNode;
                temp->val = p->val;
                temp->next = NULL;
                if (head1 == NULL)
                {
                    head1 = temp;
                }
                else
                {
                    ListNode *q = head1;
                    while (q->next != NULL)
                    {
                        q = q->next;
                    }
                    q->next = temp;
                }
            }
            p = p->next;
            i++;
        }

        return head1;
    }
};

This solution is not optimized as it uses O(n^2) time complexity but it uses as extra space of O(n). And we need to iterate over the linked list twice.

class Solution
{
public:
    ListNode *oddEvenList(ListNode *head)
    {

        ListNode *head1 = NULL;

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

        ListNode *p = head;
        int i = 2;
        ListNode *temp = new ListNode;
        temp->val = p->val;
        temp->next = NULL;
        
        head1 = temp;
        ListNode *x = head1;
        p = p->next;
        
        while (p != NULL)
        {
            if (i % 2 != 0)
            {
                ListNode *temp = new ListNode;
                temp->val = p->val;
                temp->next = NULL;

                x->next = temp;
                x = x->next;
            }
            p = p->next;
            i++;
        }

        i = 1;
        p = head;
        while (p != NULL)
        {
            if (i % 2 == 0)
            {
                ListNode *temp = new ListNode;
                temp->val = p->val;
                temp->next = NULL;

                x->next = temp;
                x = x->next;
            }
            p = p->next;
            i++;
        }

        return head1;
    }
};

This solution is not optimized as it uses O(n) time complexity but it uses as extra space of O(n). And we need to iterate over the linked list twice.

Solution II : (Using 2 pointer)

class Solution
{
public:
    ListNode *oddEvenList(ListNode *head)
    {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *evenHead = head->next;
        ListNode *oddHead = head;

        ListNode *p = evenHead;
        ListNode *q = oddHead;

        while (p != NULL && p->next != NULL)
        {
            q->next = q->next->next;
            p->next = p->next->next;
            q = q->next;
            p = p->next;
        }
        q->next = evenHead;
        return head;
    }
};

Time Complexity: O(n) , Space Complexity: O(1)