LinkedListProblem 34 of 36

Segregate even and odd nodes in a Linked List

Segregate Even and Odd Nodes in a Linked List

Problem Statement

Given a linked list of integers, segregate even and odd nodes. All even nodes should come before odd nodes while maintaining the relative order of even and odd nodes separately.

Example

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 Output: 2 -> 4 -> 6 -> 8 -> 1 -> 3 -> 5 -> 7 Input: 8 -> 12 -> 10 -> 5 -> 4 -> 1 -> 6 Output: 8 -> 12 -> 10 -> 4 -> 6 -> 5 -> 1

Brute Force Approach

Intuition

Create two separate arrays - one for even values and one for odd values. Traverse the list, segregate values, then rebuild the list.

Algorithm

  1. Traverse the list and collect even values in one array, odd values in another
  2. Create a new list by first adding all even values, then odd values
  3. Return the new head

Code

java
import java.util.ArrayList;
import java.util.List;

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SegregateEvenOddBrute {
    public static Node segregateBruteForce(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        List<Integer> evens = new ArrayList<>();
        List<Integer> odds = new ArrayList<>();
        
        // Collect values
        Node temp = head;
        while (temp != null) {
            if (temp.data % 2 == 0) {
                evens.add(temp.data);
            } else {
                odds.add(temp.data);
            }
            temp = temp.next;
        }
        
        // Rebuild list
        temp = head;
        
        // First put evens
        for (int val : evens) {
            temp.data = val;
            temp = temp.next;
        }
        
        // Then put odds
        for (int val : odds) {
            temp.data = val;
            temp = temp.next;
        }
        
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Two passes through the list
  • Space Complexity: O(n) - Arrays to store values

Optimal Approach (Change Links)

Intuition

Maintain two separate lists - one for even nodes and one for odd nodes. Traverse the original list once, appending each node to the appropriate list. Finally, connect the even list's tail to odd list's head.

Algorithm

  1. Create dummy heads for even and odd lists
  2. Traverse original list:
    • If node value is even, append to even list
    • Else append to odd list
  3. Connect even list tail to odd list head
  4. Set odd list tail's next to null
  5. Return even list head (or odd if no evens)

Code

java
class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SegregateEvenOddOptimal {
    public static Node segregateOptimal(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Dummy nodes for even and odd lists
        Node evenDummy = new Node(0);
        Node oddDummy = new Node(0);
        
        Node evenTail = evenDummy;
        Node oddTail = oddDummy;
        
        Node curr = head;
        
        // Segregate nodes
        while (curr != null) {
            if (curr.data % 2 == 0) {
                evenTail.next = curr;
                evenTail = evenTail.next;
            } else {
                oddTail.next = curr;
                oddTail = oddTail.next;
            }
            curr = curr.next;
        }
        
        // Connect even list to odd list
        evenTail.next = oddDummy.next;
        
        // Terminate odd list
        oddTail.next = null;
        
        // Get the new head
        Node newHead = (evenDummy.next != null) ? evenDummy.next : oddDummy.next;
        
        return newHead;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node createList(int[] arr) {
        if (arr.length == 0) return null;
        Node head = new Node(arr[0]);
        Node curr = head;
        for (int i = 1; i < arr.length; i++) {
            curr.next = new Node(arr[i]);
            curr = curr.next;
        }
        return head;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        Node head = createList(arr);
        
        System.out.print("Original list: ");
        printList(head);
        
        head = segregateOptimal(head);
        
        System.out.print("After segregation: ");
        printList(head);
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through the list
  • Space Complexity: O(1) - Only using constant extra space (dummy nodes)

Variation: Segregate by Position (Odd-Even Index)

Sometimes the problem asks to segregate by position (odd indices vs even indices):

Key Takeaways

  1. Two-List Approach: Create separate lists and merge - clean and efficient
  2. Dummy Nodes: Simplify edge case handling (empty lists)
  3. Maintain Order: Both approaches preserve relative order within groups
  4. Single Pass: Optimal solution only needs one traversal
  5. Space Optimization: Link manipulation avoids O(n) extra space
  6. Connection Point: Even list tail connects to odd list head
  7. Null Termination: Remember to set the last node's next to null
  8. Similar Pattern: Same technique used for sort 0s, 1s, 2s in linked list
  9. Variation Awareness: Know the difference between value-based and index-based segregation
Previous
Delete nodes which have a greater value on right side
Next
Program for nth node from the end of a Linked List