Problem

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 that 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.

Examples

Example 1:

---
title: Input
---

 graph LR
   A[1]:::odd --> B[2]:::even --> C[3]:::odd --> D[4]:::even --> E[5]:::odd
 
   classDef odd fill:#ffcc00,stroke:#000,stroke-width:2px; 
   classDef even fill:#add8e6,stroke:#000,stroke-width:2px;
  
---
title: Output
---

 graph LR
   A[1]:::odd --> C[3]:::odd --> E[5]:::odd --> B[2]:::even --> D[4]:::even
 
   classDef odd fill:#ffcc00,stroke:#000,stroke-width:2px; 
   classDef even fill:#add8e6,stroke:#000,stroke-width:2px;
  
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

---
title: Input
---

 graph LR
   A[2]:::odd --> B[1]:::even --> C[3]:::odd --> D[5]:::even --> E[6]:::odd --> F[4]:::even --> G[7]:::odd
 
   classDef odd fill:#ffcc00,stroke:#000,stroke-width:2px; 
   classDef even fill:#add8e6,stroke:#000,stroke-width:2px;
  
---
title: Output
---

 graph LR
   A[2]:::odd --> C[3]:::odd --> E[6]:::odd --> G[7]:::odd --> B[1]:::even --> D[5]:::even --> F[4]:::even
 
   classDef odd fill:#ffcc00,stroke:#000,stroke-width:2px; 
   classDef even fill:#add8e6,stroke:#000,stroke-width:2px;
  
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Solution

Method 1 - Using 2 Pointers

This problem can be addressed by utilizing two pointers. By iterating through the linked list, we can advance both pointers accordingly.

Here is the approach:

  1. Initialize Pointers:
    • Use two pointers, odd and even, to track the current nodes in the odd and even lists.
    • Use dummy nodes to start the odd and even lists.
  2. Traverse the Linked List:
    • Traverse through the linked list, and add each odd-indexed node to the odd list and each even-indexed node to the even list.
  3. Connect the Lists:
    • After traversing the entire linked list, connect the last node in the odd list to the head of the even list.
  4. Return the Head of the Odd List:
    • Return the head of the reordered linked list, which starts with the nodes grouped by odd indices followed by even indices.

Code

Java
public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null)
            return null;

        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead =
            even; // To connect the end of odd list to the head of even list

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

        odd.next = evenHead; // Connect odd list to even list
        return head;
    }
}
Python
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return None

        odd = head
        even = head.next
        evenHead = (
            even  # To connect the end of odd list to the head of even list
        )

        while even and even.next:
            odd.next = even.next  # Odd nodes
            odd = odd.next
            even.next = odd.next  # Even nodes
            even = even.next

        odd.next = evenHead  # Connect odd list to even list
        return head

Complexity

  • ⏰ Time complexity: O(n), where n is the total number of nodes in the linked list. We traverse the list once.
  • 🧺 Space complexity: O(1), since only a constant amount of extra space is used for the pointers.