{x}
blog image

Odd Even Linked List

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • The number of nodes in the linked list is in the range [0, 104].
  • -106 <= Node.val <= 106

Solution Explanation: Odd Even Linked List

The problem requires rearranging a linked list so that all nodes with odd indices appear before nodes with even indices, maintaining the original order within each group. The solution must be achieved with O(1) extra space and O(n) time complexity.

Approach: Single Pass with Pointers

The optimal approach involves a single pass through the linked list using three pointers:

  1. odd: Points to the tail of the odd-indexed nodes.
  2. even: Points to the tail of the even-indexed nodes.
  3. evenHead: Stores the head of the even-indexed nodes for later concatenation.

The algorithm iterates through the list. For each node:

  • If the node's index is odd, append it to the odd tail.
  • If the node's index is even, append it to the even tail.

Finally, it connects the odd tail to the evenHead to create the rearranged list.

Time and Space Complexity

  • Time Complexity: O(n), as the algorithm iterates through the linked list once.
  • Space Complexity: O(1), as only a constant number of pointers are used.

Code Implementation (Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
 
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:  # Handle empty or single-node lists
            return head
 
        odd = head
        even = head.next
        evenHead = even  # Store the head of the even sublist
 
        while even and even.next:
            odd.next = even.next  # Connect odd tail to the next odd node
            odd = odd.next
            even.next = odd.next  #Connect even tail to the next even node
            even = even.next
 
        odd.next = evenHead  # Connect the odd tail to the head of the even sublist
 
        return head

Code Implementation in Other Languages

The logic remains the same across different languages; only syntax changes. The provided solution includes examples in Java, C++, Go, and TypeScript. The core idea of using three pointers to manage odd and even sublists remains consistent.

Key improvements in the provided code compared to a naive approach:

  • Handles edge cases: It explicitly checks for empty or single-node lists, preventing errors.
  • Efficiency: It avoids unnecessary iterations or temporary data structures.
  • Clarity: The code is well-structured and easy to follow.

The provided multi-language solution demonstrates the elegance and efficiency of this single-pass pointer manipulation technique. The consistency of the approach across languages highlights its fundamental nature in solving this linked list problem.