Odd Even Linked List - Practice Coding Problems

Odd Even Linked List - Problem

Linked List Medium

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note: The relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Input & Output

Example 1 — Basic Case

$ Input: head = [1,2,3,4,5]

› Output: [1,3,5,2,4]

💡 Note: Group odd indices (1st, 3rd, 5th nodes) first: [1,3,5], then even indices (2nd, 4th nodes): [2,4]. Final result: [1,3,5,2,4]

Example 2 — Even Length

$ Input: head = [2,1,3,5,6,4,7]

› Output: [2,3,6,7,1,5,4]

💡 Note: Odd positions (1st,3rd,5th,7th): [2,3,6,7], even positions (2nd,4th,6th): [1,5,4]. Result: [2,3,6,7,1,5,4]

Example 3 — Two Nodes

$ Input: head = [1,2]

› Output: [1,2]

💡 Note: Only two nodes: 1st node (odd) stays first, 2nd node (even) stays second. Order unchanged.

Constraints

The number of nodes in the linked list is in the range [0, 10⁴]
-10⁶ ≤ Node.val ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Original linked list [1,2,3,4,5]

Group by Position

Separate odd positions (1,3,5) and even positions (2,4)

Output

Rearranged list [1,3,5,2,4]

Key Takeaway

🎯 Key Insight: Maintain two separate chains for odd and even positioned nodes, then connect them to achieve O(1) space complexity

Asked in

F Facebook 35 M Microsoft 28 A Amazon 22 G Google 18

The key insight is to maintain separate pointers for odd and even positioned nodes, rearranging the linked list in-place by connecting alternate nodes into two separate chains, then joining them. Best approach uses two pointers for O(1) space and O(n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Array Conversion	O(n)	O(n)	Convert linked list to array, rearrange, then rebuild list
Two-Pointer In-Place Rearrangement	O(n)	O(1)	Use two pointers to separate odd and even nodes in a single pass

Array Conversion — Algorithm Steps

Step 1: Traverse list and store values in array
Step 2: Create new array with odd indices first, then even indices
Step 3: Build new linked list from rearranged array

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Values

Store all node values in array

Separate by Index

Group odd indices [0,2,4...] then even [1,3,5...]

Rebuild List

Create new linked list from rearranged array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = createNode(arr[0]);
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createNode(arr[i]);
        current = current->next;
    }
    return head;
}

int listToArray(struct ListNode* head, int* arr) {
    int size = 0;
    struct ListNode* current = head;
    while (current) {
        arr[size++] = current->val;
        current = current->next;
    }
    return size;
}

struct ListNode* solution(struct ListNode* head) {
    if (!head || !head->next) return head;
    
    // Convert to array
    int values[1000];
    int size = listToArray(head, values);
    
    // Rearrange: odd indices first, then even indices
    int result[1000];
    int idx = 0;
    
    // Add odd positioned elements (0, 2, 4, ...)
    for (int i = 0; i < size; i += 2) {
        result[idx++] = values[i];
    }
    // Add even positioned elements (1, 3, 5, ...)
    for (int i = 1; i < size; i += 2) {
        result[idx++] = values[i];
    }
    
    // Convert back to linked list
    return arrayToList(result, size);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array from input
    int arr[1000];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            arr[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    int output[1000];
    int outputSize = listToArray(result, output);
    
    printf("[");
    for (int i = 0; i < outputSize; i++) {
        printf("%d", output[i]);
        if (i < outputSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to read values, single pass to create new list

✓ Linear Growth

Space Complexity

O(n)

Array to store all node values

⚡ Linearithmic Space

236.6K Views

Medium Frequency

~15 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Array Conversion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler