Given the head of a singly linked list, rearrange the nodes so all even-valued nodes appear before all odd-valued nodes. Relative order inside the even group and inside the odd group must remain unchanged.
Node values decide the grouping, not node positions. Return the head of the rearranged linked list after segregation finishes.
Example 1
Input: head = [1, 2, 3, 4, 5, 6]
Output: [2, 4, 6, 1, 3, 5]
Explanation: Even-valued nodes keep original even-group order, and odd-valued nodes keep original odd-group order.
Example 2
Input: head = [7, 5, 3]
Output: [7, 5, 3]
Explanation: All nodes are odd, so original order remains unchanged.
Brute Force Approach
A simple way to think about the segregation is to collect even values first and odd values later, then rebuild the linked list in the new order. One straight traversal scans the chain and drops values into two arrays. A second phase writes even values back first and writes odd values in the remaining nodes.
Algorithm
Initialize one array for even values and another for odd values, as separating the values makes it straightforward to place all even elements before the odd ones.
Traverse the linked list once and place each node value into the corresponding array, based on whether the value is even or odd.
Reset a traversal pointer to
head, since the same linked-list nodes will be reused while only their values are being rearranged.Traverse the even-value array and overwrite the linked-list node values from left to right, which places all even values at the beginning of the list.
Continue traversing through the remaining nodes using the odd-value array, so the odd values occupy the positions after all even values.
Return the original
head, as the structure of the linked list remains unchanged and only the node values have been reordered.
Dry Run
segrigate even odd
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; Node(int value) { data = value; next = nullptr; }};class Solution {public: // Segregate even and odd node values by collecting and rewriting. Node* segregate(Node* head) { // Return early for an empty list. if (head == nullptr) { return head; } // Store even values in encounter order. vector<int> evenValues; // Store odd values in encounter order. vector<int> oddValues; // Traverse the list once and collect values. Node* current = head; while (current != nullptr) { if (current->data % 2 == 0) { evenValues.push_back(current->data); } else { oddValues.push_back(current->data); } current = current->next; } // Reset traversal for value rewriting. current = head; // Write all even values first. for (int value : evenValues) { current->data = value; current = current->next; } // Write all odd values after even values finish. for (int value : oddValues) { current->data = value; current = current->next; } // Return the updated head. return head; }};// Build a linked list from an array.Node* buildList(const vector<int>& values) { Node* dummy = new Node(0); Node* tail = dummy; for (int value : values) { tail->next = new Node(value); tail = tail->next; } return dummy->next;}// Print the linked list in one line.void printList(Node* head) { while (head != nullptr) { cout << head->data; if (head->next != nullptr) { cout << " "; } head = head->next; } cout << "\n";}// Run the array-based solution on a hard-coded sample.int main() { vector<int> values = {1, 2, 3, 4, 5, 6}; Node* head = buildList(values); Solution solution; Node* answer = solution.segregate(head); printList(answer); return 0;}Complexity Analysis
Time Complexity: O(N), one traversal collects values and one traversal rewrites values.
Space Complexity: O(N), extra arrays store even and odd values separately.
Optimal Approach
A cleaner linked-list solution keeps node order intact without extra arrays. One straight traversal pulls each visited node into one of two growing chains: an even chain and an odd chain. After the scan finishes, the tail of the even chain connects to the head of the odd chain.
Algorithm
Initialize two dummy nodes and two tail pointers for the even and odd chains, as separate chains make it possible to preserve the original relative order within each group.
Traverse the linked list once from
headto the end, since every node needs to be classified as either even or odd.Detach the current node from the remaining chain before appending it, as this prevents its old connection from interfering with the newly formed chains.
Append the current node to the even chain when its value is even, since all such nodes need to appear before the odd nodes.
Append the current node to the odd chain when its value is odd, preserving the order in which odd nodes were encountered.
Link the tail of the even chain to the head of the odd chain after traversal, which combines both chains while keeping all even nodes before the odd nodes.
Set the odd tail's
nextpointer tonull, as the last odd node should become the final node of the reordered list.Return the head of the even chain when at least one even node exists; otherwise return the head of the odd chain, since there may be no even nodes to form the first part of the list.
Dry Run
segrigate even odd
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; Node(int value) { data = value; next = nullptr; }};class Solution {public: // Segregate nodes by relinking two stable chains in place. Node* segregate(Node* head) { // Return early for empty or single-node lists. if (head == nullptr || head->next == nullptr) { return head; } // Dummy head for the even chain. Node* evenDummy = new Node(0); // Dummy head for the odd chain. Node* oddDummy = new Node(0); // Tail pointer for the even chain. Node* evenTail = evenDummy; // Tail pointer for the odd chain. Node* oddTail = oddDummy; // Current pointer scans the original chain. Node* current = head; // Traverse once and move nodes into the proper chain. while (current != nullptr) { // Store the next node before detaching the current node. Node* front = current->next; // Break the current link before appending. current->next = nullptr; // Append the node to the even chain when the value is even. if (current->data % 2 == 0) { evenTail->next = current; evenTail = current; } else { // Append the node to the odd chain when the value is odd. oddTail->next = current; oddTail = current; } // Move to the next original node. current = front; } // Join the even chain with the odd chain. evenTail->next = oddDummy->next; // Return the even-chain head when even nodes exist. if (evenDummy->next != nullptr) { return evenDummy->next; } // Return the odd-chain head when no even node exists. return oddDummy->next; }};// Build a linked list from an array.Node* buildList(const vector<int>& values) { Node* dummy = new Node(0); Node* tail = dummy; for (int value : values) { tail->next = new Node(value); tail = tail->next; } return dummy->next;}// Print the linked list in one line.void printList(Node* head) { while (head != nullptr) { cout << head->data; if (head->next != nullptr) { cout << " "; } head = head->next; } cout << "\n";}// Run the in-place solution on a hard-coded sample.int main() { vector<int> values = {1, 2, 3, 4, 5, 6}; Node* head = buildList(values); Solution solution; Node* answer = solution.segregate(head); printList(answer); return 0;}Complexity Analysis
Time Complexity: O(N), one traversal visits every node once.
Space Complexity: O(1), only a fixed number of pointers and dummy nodes are used.
Interview follow-up Questions
Grouping depends on node values, so even-valued nodes move before odd-valued nodes.
Be the first to add a comment.