English flagEnglish  
CLOSE

Suggested:

Problem Statement

Given a singly linked list, the task is to segregate its nodes in such a way that all nodes with even values appear before all nodes with odd values. The relative order of even and odd elements should remain the same.

Examples

Example 1:

Input: List = [1, 2, 3, 4, 5, 6]
Output: [1, 3, 5, 2, 4, 6]
Example 2:

Input Linked List: [17, 15, 8, 12, 10, 5, 4]
Output Linked List: [8, 12, 10, 4, 17, 15, 5]

Different Approaches

1️⃣ Using Two Separate Lists

To segregate the odd and even nodes, we can traverse the linked list while maintaining two separate lists - one for even nodes and one for odd nodes. After traversing the entire list, we can simply append the odd list after the even list to achieve the desired segregation.

Algorithm:

  1. Traverse the linked list, maintaining two separate lists for even and odd nodes.
  2. After traversal, append the odd list after the even list.
  3. This approach requires extra space for maintaining separate lists.

Complexity Analysis:

  • Time Complexity: O(n)
  • Space Complexity: O(n)

2️⃣ In-Place Rearrangement

Intuition

The problem requires rearranging a linked list so that all nodes with even values appear before all nodes with odd values while maintaining their relative order. The key idea is to traverse the list once, separate nodes into two categories (even and odd), and then combine these two categories into a single linked list.

The intuition behind solving this efficiently involves using two pointers to build two separate lists during a single pass through the original list:

  • Even List: Contains all nodes with even values.
  • Odd List: Contains all nodes with odd values.

After creating these two lists, they can be connected such that all even nodes come before all odd nodes.

Algorithm:

  1. Initialize Pointers:
    1. Use four pointers to manage two lists: one for even nodes and one for odd nodes.
    2. evenHead and oddHead are dummy nodes that will mark the beginning of the even and odd lists, respectively.
    3. evenTail and oddTail are pointers that will traverse and expand the even and odd lists, respectively.
  2. Traverse the Original List:
    1. Start from the head of the original linked list.
    2. For each node:
      1. If the node's value is even, append it to the end of the even list and move the evenTail pointer forward.
      2. If the node's value is odd, append it to the end of the odd list and move the oddTail pointer forward.
  3. Combine the Even and Odd Lists:
    1. After traversing all nodes, connect the end of the even list (evenTail) to the start of the odd list (oddHead->next).
    2. Ensure the end of the odd list (oddTail->next) points to NULL to mark the end of the combined list.
  4. Update the Head of the Linked List:
    1. If the even list is non-empty, set the head to evenHead->next.
    2. If there are no even nodes, set the head to oddHead->next.

Dry Run:

Let's perform a dry run using the example linked list:

Input Linked List:
17 -> 15 -> 8 -> 12 -> 10 -> 5 -> 4

Expected Output Linked List:
8 -> 12 -> 10 -> 4 -> 17 -> 15 -> 5

Initialization:
evenHead = nullptr
evenTail = nullptr
oddHead = nullptr
oddTail = nullptr

+----+  +----+  +---+  +----+  +----+  +---+  +---+
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
+----+  +----+  +---+  +----+  -----+  +---+  +---+
1st Iteration:
------  ------  -----  ------  ------  -----  -----
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
------  ------  -----  ------  ------  -----  -----
  ^
  |
current

evenHead = nullptr
evenTail = nullptr
oddHead = 17
oddTail = 17
Second Iteration:
------  ------  -----  ------  ------  -----  -----
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
------  ------  -----  ------  ------  -----  -----
          ^
          |
         current

evenHead = nullptr
evenTail = nullptr
oddHead = 17
oddTail = 17 -> 15
Third Iteration:
------  ------  -----  ------  ------  -----  -----
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
------  ------  -----  ------  ------  -----  -----
                  ^
                  |
                current

evenHead = 8
evenTail = 8
oddHead = 17
oddTail = 17 -> 15
Fourth Iteration:
------  ------  -----  ------  ------  -----  -----
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
------  ------  -----  ------  ------  -----  -----
                          ^
                          |
                         current

evenHead = 8
evenTail = 8 -> 12
oddHead = 17
oddTail = 17 -> 15
Fifth Iteration:
------  ------  -----  ------  ------  -----  -----
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
------  ------  -----  ------  ------  -----  -----
                                  ^
                                  |
                                current

evenHead = 8
evenTail = 8 -> 12 -> 10
oddHead = 17
oddTail = 17 -> 15
Sixth Iteration:
------  ------  -----  ------  ------  -----  -----
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
------  ------  -----  ------  ------  -----  -----
                                         ^
                                         |
                                        current

evenHead = 8
evenTail = 8 -> 12 -> 10
oddHead = 17
oddTail = 17 -> 15 -> 5
Seventh Iteration:
------  ------  -----  ------  ------  -----  -----
| 17 |->| 15 |->| 8 |->| 12 |->| 10 |->| 5 |->| 4 |
------  ------  -----  ------  ------  -----  -----
                                                ^
                                                |
                                               current

evenHead = 8
evenTail = 8 -> 12 -> 10 -> 4
oddHead = 17
oddTail = 17 -> 15 -> 5
Break of Loop:
-----  -----  ----  -----  -----  ----  ----
|17 |->|15 |->|8 |->|12 |->|10 |->|5 |->|4 | -> nullptr
-----  -----  ----  -----  -----  ----  ----
                                                   ^
                                                   |
                                                current

Since current is pointing to nullptr,
so break the loop and merge the odd and even list.

evenHead = 8
evenTail = 8 -> 12 -> 10 -> 4
oddHead = 17
oddTail = 17 -> 15 -> 5

evenTail->next = oddHead
oddTail->next = nullptr

8 -> 12 -> 10 -> 4 -> 17 -> 15 -> 5 -> nullptr

Code:

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

void segregateEvenOdd(Node* head) {
    Node* evenHead = nullptr, *evenTail = nullptr;
    Node* oddHead = nullptr, *oddTail = nullptr;

    Node* current = head;

    while (current != nullptr) {
        if (current->data % 2 == 0) {
            if (evenHead == nullptr) {
                evenHead = evenTail = current;
            } else {
                evenTail->next = current;
                evenTail = current;
            }
        } else {
            if (oddHead == nullptr) {
                oddHead = oddTail = current;
            } else {
                oddTail->next = current;
                oddTail = current;
            }
        }
        current = current->next;
    }

    if (evenHead == nullptr || oddHead == nullptr)
        return;

    evenTail->next = oddHead;
    oddTail->next = nullptr;

    // Update head to the beginning of even list
    head = evenHead;
}

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Example usage
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    cout << "Original List: ";
    printList(head);

    segregateEvenOdd(head);

    cout << "Segregated List: ";
    printList(head);

    return 0;
}
OR:
/*
Definition of singly linked list:
struct ListNode
{
    int val;               // Value of the node
    ListNode *next;        // Pointer to the next node in the list

    // Default constructor
    ListNode() {
        val = 0;
        next = NULL;
    }

    // Constructor to initialize the node with a value
    ListNode(int data1) {
        val = data1;
        next = NULL;
    }

    // Constructor to initialize the node with a value and the next pointer
    ListNode(int data1, ListNode *next1) {
        val = data1;
        next = next1;
    }
};
*/

class Solution {
public:
    // Function to rearrange the list such that odd-indexed nodes appear first
    // followed by even-indexed nodes
    ListNode* oddEvenList(ListNode* head) {
        // Dummy node to start the list of odd-indexed nodes
        ListNode* oddIndex = new ListNode(0);
        ListNode* oddIndexItr = oddIndex; // Iterator for the odd-indexed list

        // Dummy node to start the list of even-indexed nodes
        ListNode* evenIndex = new ListNode(0);
        ListNode* evenIndexItr = evenIndex; // Iterator for the even-indexed list

        ListNode* iterator = head; // Iterator for traversing the input list
        int count = 1; // Counter to determine odd or even index

        // Traverse the input list
        while (iterator != nullptr) {
            // Create a new node for the current value (unnecessary memory usage here)
            ListNode* temp = new ListNode(iterator->val);

            if (count % 2 == 1) {
                // Current node is at an odd index
                oddIndexItr->next = temp;    // Add the node to the odd-indexed list
                oddIndexItr = oddIndexItr->next; // Move the iterator
            } else {
                // Current node is at an even index
                evenIndexItr->next = temp;   // Add the node to the even-indexed list
                evenIndexItr = evenIndexItr->next; // Move the iterator
            }

            iterator = iterator->next; // Move to the next node in the input list
            count++; // Increment the index counter
        }

        // Connect the last odd-indexed node to the first even-indexed node
        oddIndexItr->next = evenIndex->next;

        // Return the head of the rearranged list (skipping the dummy node)
        return oddIndex->next;
    }
};

Complexity Analysis:

  • Time Complexity: O(n)
    • This is because we traverse the list once to segregate the even and odd nods, where n is the number of nodes in the linked list.
  • Space Complexity: O(1)
    • For in-place rearrangement approach O(1)

3️⃣ Optimized Approach

Code:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) {
            // If the list has less than two nodes, return as is
            return head;
        }

        // Pointers to track odd and even nodes
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even; // Store the head of the even list

        // Traverse and rearrange nodes
        while (even && even->next) {
            odd->next = even->next;  // Connect the next odd node
            odd = odd->next;         // Move odd pointer forward

            even->next = odd->next;  // Connect the next even node
            even = even->next;       // Move even pointer forward
        }

        // Connect the last odd node to the head of the even list
        odd->next = evenHead;

        return head; // Return the rearranged list
    }
};

Complexity Analysis:

  • Time Complexity: O(N/2)x2 ~ O(N) because we are iterating over the odd-indexed as well as the even-indexed elements. Here N is the size of the given linked list.
  • Space Complexity: O(1) because we have not used any extra space.

Your experience on this site will be improved by allowing cookies Cookie Policy