Segregate odd and even nodes in LL

Intuition

The simplest way to approach this problem is to traverse the linked list, gather the elements at odd and even indices into separate lists, and then create a new linked list from these lists.

Approach

Initialize a temporary pointer to the head of the linked list for traversal. Create a list to store the grouped odd-indexed and even-indexed elements. Traverse the linked list, adding the data from each odd-indexed node to the list, then reset the pointer to the second node and repeat the process for even-indexed nodes.
Traverse the linked list again, replacing each node’s value with the values stored in the list in order.

Dry Run

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode() {
        val = 0;
        next = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1) {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to segragate odd and even indices nodes
    ListNode* oddEvenList(ListNode* head) {
        // Check if list is empty or has only one node
        if (head == NULL || head->next == NULL)
            return head;

        // To store values
        vector<int> array;   
        ListNode* temp = head;

        /*Traverse the list, skipping one node, 
        and store values in the vector*/
        while (temp != NULL && temp->next != NULL) {
            array.push_back(temp->val);
            temp = temp->next->next;
        }

        /*If there's an even number 
        of nodes, add the value
         of the last node*/
        if (temp != NULL)
            array.push_back(temp->val);

        // Reset temp 
        temp = head->next;

        /*Traverse the list again, skipping one node 
       and store values 
        in the vector*/
        while (temp != NULL && temp->next != NULL) {
            array.push_back(temp->val);
            temp = temp->next->next;
        }

       /* If there's an odd number
        of nodes, add the 
        value of the last node*/
        if (temp != NULL)
            array.push_back(temp->val);

        // Reset temp 
        temp = head;
        int i = 0;

        // Update node values 
        while (temp != NULL) {
            temp->val = array[i];
            temp = temp->next;
            i++;
        }

        return head;
    }
};

// Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

// Main function
int main() {
    // Create a linked list with given values
    vector<int> arr = {1, 3, 4, 2, 5, 6};
    ListNode* head = new ListNode(arr[0]);
    head->next = new ListNode(arr[1]);
    head->next->next = new ListNode(arr[2]);
    head->next->next->next = new ListNode(arr[3]);
    head->next->next->next->next = new ListNode(arr[4]);
    head->next->next->next->next->next = new ListNode(arr[5]);

    // Rearrange the list and print it
    Solution solution;
    head = solution.oddEvenList(head);
    printLL(head);

    return 0;
}
import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode() {
        val = 0;
        next = null;
    }
    ListNode(int data1) {
        val = data1;
        next = null;
    }
    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Function to segregate odd and even indices nodes
    public ListNode oddEvenList(ListNode head) {
        // Check if list is empty or has only one node
        if (head == null || head.next == null)
            return head;

        // To store values
        List<Integer> array = new ArrayList<>();   
        ListNode temp = head;

        /*Traverse the list, skipping one node, 
        and store values in the vector*/
        while (temp != null && temp.next != null) {
            array.add(temp.val);
            temp = temp.next.next;
        }

        /*If there's an even number 
        of nodes, add the value
         of the last node*/
        if (temp != null)
            array.add(temp.val);

        // Reset temp 
        temp = head.next;

        /*Traverse the list again, skipping one node,
         and store values 
        in the vector*/
        while (temp != null && temp.next != null) {
            array.add(temp.val);
            temp = temp.next.next;
        }

       /* If there's an odd number
        of nodes, add the 
        value of the last node*/
        if (temp != null)
            array.add(temp.val);

        // Reset temp 
        temp = head;
        int i = 0;

        // Update node values 
        while (temp != null) {
            temp.val = array.get(i);
            temp = temp.next;
            i++;
        }

        return head;
    }
}

// Function to print the linked list
public static void printLL(ListNode head) {
    while (head != null) {
        System.out.print(head.val + " ");
        head = head.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    // Create a linked list with given values
    int[] arr = {1, 3, 4, 2, 5, 6};
    ListNode head = new ListNode(arr[0]);
    head.next = new ListNode(arr[1]);
    head.next.next = new ListNode(arr[2]);
    head.next.next.next = new ListNode(arr[3]);
    head.next.next.next.next = new ListNode(arr[4]);
    head.next.next.next.next.next = new ListNode(arr[5]);

    // Rearrange the list and print it
    Solution solution = new Solution();
    head = solution.oddEvenList(head);
    printLL(head);
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to segregate odd and even indices nodes
    def oddEvenList(self, head):
        # Check if list is empty or has only one node
        if not head or not head.next:
            return head

        # To store values
        array = []
        temp = head

        '''Traverse the list, skipping one node, 
        and store values in the vector'''
        while temp and temp.next:
            array.append(temp.val)
            temp = temp.next.next

        '''If there's an even number 
        of nodes, add the value
         of the last node'''
        if temp:
            array.append(temp.val)

        # Reset temp 
        temp = head.next

        '''Traverse the list again, skipping one node ,
         and store values 
        in the vector'''
        while temp and temp.next:
            array.append(temp.val)
            temp = temp.next.next

        '''If there's an odd number
        of nodes, add the 
        value of the last node'''
        if temp:
            array.append(temp.val)

        # Reset temp 
        temp = head
        i = 0

        # Update node values 
        while temp:
            temp.val = array[i]
            temp = temp.next
            i += 1

        return head

# Function to print the linked list
def printLL(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

# Main function
if __name__ == "__main__":
    # Create a linked list with given values
    arr = [1, 3, 4, 2, 5, 6]
    head = ListNode(arr[0])
    head.next = ListNode(arr[1])
    head.next.next = ListNode(arr[2])
    head.next.next.next = ListNode(arr[3])
    head.next.next.next.next = ListNode(arr[4])
    head.next.next.next.next.next = ListNode(arr[5])

    # Rearrange the list and print it
    solution = Solution()
    head = solution.oddEvenList(head)
    printLL(head)
// Definition of singly linked list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to segregate odd and even indices nodes
    oddEvenList(head) {
        // Check if list is empty or has only one node
        if (head === null || head.next === null)
            return head;

        // To store values
        const array = [];
        let temp = head;

        /*Traverse the list, skipping one node , 
        and store values in the vector*/
        while (temp !== null && temp.next !== null) {
            array.push(temp.val);
            temp = temp.next.next;
        }

        /*If there's an even number 
        of nodes, add the value
         of the last node*/
        if (temp !== null)
            array.push(temp.val);

        // Reset temp 
        temp = head.next;

        /*Traverse the list again, skipping one node ,
         and store values 
        in the vector*/
        while (temp !== null && temp.next !== null) {
            array.push(temp.val);
            temp = temp.next.next;
        }

       /* If there's an odd number
        of nodes, add the 
        value of the last node*/
        if (temp !== null)
            array.push(temp.val);

        // Reset temp 
        temp = head;
        let i = 0;

        // Update node values 
        while (temp !== null) {
            temp.val = array[i];
            temp = temp.next;
            i++;
        }

        return head;
    }
}

// Function to print the linked list
function printLL(head) {
    while (head !== null) {
        process.stdout.write(head.val + " ");
        head = head.next;
    }
    console.log();
}

// Main function
// Create a linked list with given values
const arr = [1, 3, 4, 2, 5, 6];
let head = new ListNode(arr[0]);
head.next = new ListNode(arr[1]);
head.next.next = new ListNode(arr[2]);
head.next.next.next = new ListNode(arr[3]);
head.next.next.next.next = new ListNode(arr[4]);
head.next.next.next.next.next = new ListNode(arr[5]);

// Rearrange the list and print it
const solution = new Solution();
head = solution.oddEvenList(head);
printLL(head);

Complexity Analysis

Time Complexity: O(2xN) for the following reasons:-

Traversing the odd-indexed elements takes O(N/2) time.
Traversing the even-indexed elements takes O(N/2) time.
Updating the linked list with the values from the array takes O(N) time.

Here N is the size of the linked list. Space Complexity: O(N) because an additional list is used to store the grouped elements from the linked list.

Intuition

The brute force approach utilizes additional space. To make it more effective, we can create links between all the odd-indexed and even-indexed elements while traversing the linked list and finally point the last odd-indexed element to the first even-indexed element to get the desired linked list without the help of an additional data structure.

Approach

Start by setting two pointers: one for the odd-indexed elements and one for the even-indexed elements. The odd pointer will start at the first node, and the even pointer will start at the second node. Also, keep track of the first even-indexed node.
Traverse the linked list, linking all the odd-indexed nodes together and all the even-indexed nodes together.
Depending on whether the list length is odd or even, ensure the traversal continues appropriately. For an even-length list, make sure the loop runs until the node after the even pointer is not NULL. For an odd-length list, make sure the loop runs until the even pointer itself is not NULL.
Once all nodes are grouped, link the last odd-indexed node to the first even-indexed node to form the desired linked list without using extra space.

Dry Run

#include <bits/stdc++.h>

using namespace std;

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode() {
        val = 0;
        next = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1) {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to rearrange nodes 
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next)
            return head;

        /*Initialize pointers for odd 
        and even nodes and keep 
        track of the first even node*/
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* firstEven = head->next;

        // Rearranging nodes
        while (even && even->next) {
            odd->next = odd->next->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }

       /* Connect the last odd 
       node to the first even node*/
        odd->next = firstEven;

        return head;
    }
};

// Function to print the linked list
void printLL(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

// Main function
int main() {
    // Create a linked list with given values
    vector<int> arr = {1, 3, 4, 2, 5, 6};
    ListNode* head = new ListNode(arr[0]);
    head->next = new ListNode(arr[1]);
    head->next->next = new ListNode(arr[2]);
    head->next->next->next = new ListNode(arr[3]);
    head->next->next->next->next = new ListNode(arr[4]);
    head->next->next->next->next->next = new ListNode(arr[5]);

    // Print the original linked list
    cout << "Original Linked List: ";
    printLL(head);
    cout << '\n';

    // Rearrange the list and print it
    Solution solution;
    head = solution.oddEvenList(head);
    cout << "New Linked List: ";
    printLL(head);

    return 0;
}
import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode() {
        val = 0;
        next = null;
    }
    ListNode(int data1) {
        val = data1;
        next = null;
    }
    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Function to rearrange nodes
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        /*Initialize pointers for odd 
        and even nodes and keep 
        track of the first even node*/
        ListNode odd = head;
        ListNode even = head.next;
        ListNode firstEven = head.next;

        // Rearranging nodes
        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            even.next = even.next.next;
            odd = odd.next;
            even = even.next;
        }

        /* Connect the last odd 
       node to the first even node*/
        odd.next = firstEven;

        return head;
    }
}

// Function to print the linked list
public static void printLL(ListNode head) {
    while (head != null) {
        System.out.print(head.val + " ");
        head = head.next;
    }
    System.out.println();
}

// Main function
public static void main(String[] args) {
    // Create a linked list with given values
    int[] arr = {1, 3, 4, 2, 5, 6};
    ListNode head = new ListNode(arr[0]);
    head.next = new ListNode(arr[1]);
    head.next.next = new ListNode(arr[2]);
    head.next.next.next = new ListNode(arr[3]);
    head.next.next.next.next = new ListNode(arr[4]);
    head.next.next.next.next.next = new ListNode(arr[5]);

    // Print the original linked list
    System.out.println("Original Linked List: ");
    printLL(head);

    // Rearrange the list and print it
    Solution solution = new Solution();
    head = solution.oddEvenList(head);
    System.out.println("New Linked List: ");
    printLL(head);
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to rearrange nodes
    def oddEvenList(self, head):
        if not head or not head.next:
            return head

        '''Initialize pointers for odd 
        and even nodes and keep 
        track of the first even node'''
        odd = head
        even = head.next
        firstEven = head.next

        # Rearranging nodes
        while even and even.next:
            odd.next = odd.next.next
            even.next = even.next.next
            odd = odd.next
            even = even.next

        ''' Connect the last odd 
       node to the first even node'''
        odd.next = firstEven

        return head

# Function to print the linked list
def printLL(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

# Main function
if __name__ == "__main__":
    # Create a linked list with given values
    arr = [1, 3, 4, 2, 5, 6]
    head = ListNode(arr[0])
    head.next = ListNode(arr[1])
    head.next.next = ListNode(arr[2])
    head.next.next.next = ListNode(arr[3])
    head.next.next.next.next = ListNode(arr[4])
    head.next.next.next.next.next = ListNode(arr[5])

    # Print the original linked list
    print("Original Linked List: ", end="")
    printLL(head)

    # Rearrange the list and print it
    solution = Solution()
    head = solution.oddEvenList(head)
    print("New Linked List: ", end="")
    printLL(head)
// Definition of singly linked list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to rearrange nodes
    oddEvenList(head) {
        if (!head || !head.next)
            return head;

        /*Initialize pointers for odd 
        and even nodes and keep 
        track of the first even node*/
        let odd = head;
        let even = head.next;
        let firstEven = head.next;

        // Rearranging nodes
        while (even && even.next) {
            odd.next = odd.next.next;
            even.next = even.next.next;
            odd = odd.next;
            even = even.next;
        }

        /* Connect the last odd 
       node to the first even node*/
        odd.next = firstEven;

        return head;
    }
}

// Function to print the linked list
function printLL(head) {
    while (head) {
        process.stdout.write(head.val + " ");
        head = head.next;
    }
    console.log();
}

// Main function
// Create a linked list with given values
const arr = [1, 3, 4, 2, 5, 6];
let head = new ListNode(arr[0]);
head.next = new ListNode(arr[1]);
head.next.next = new ListNode(arr[2]);
head.next.next.next = new ListNode(arr[3]);
head.next.next.next.next = new ListNode(arr[4]);
head.next.next.next.next.next = new ListNode(arr[5]);

// Print the original linked list
console.log("Original Linked List: ");
printLL(head);

// Rearrange the list and print it
const solution = new Solution();
head = solution.oddEvenList(head);
console.log("New Linked List: ");
printLL(head);

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.

Problem List

Segregate odd and even nodes in LL

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code