LeetCode Solutions Blog

Odd Even Linked List

Number: 328

Difficulty: Medium

Paid? No

Problem Description

(Group all odd-indexed nodes together followed by even-indexed nodes in a singly linked list, preserving the relative order within each group.)

Key Insights

Use two pointers: one for odd-indexed nodes and one for even-indexed nodes.
The first node is considered odd, and the second node is even.
Traverse the list once, reassigning the next pointers to segregate odd and even nodes.
Finally, attach the even list at the end of the odd list.
The solution must use O(1) extra space and O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n) since the list is traversed once. Space Complexity: O(1) as only a few pointers are used.

Solution

Maintain two pointers, odd and even, starting from the head and head.next, respectively. As you iterate, update odd.next to point to the next odd element (skipping an even node) and even.next to point to the next even element. Once the end is reached, attach the even list to the end of the odd list. This in-place rearrangement preserves the initial ordering within odd and even groups while meeting the space and time constraints.

Code Solutions

# 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: ListNode) -> ListNode:
        # Check for empty list or list with one node.
        if not head or not head.next:
            return head
        
        odd = head             # Point to the first (odd indexed) node.
        even = head.next       # Point to the second (even indexed) node.
        even_head = even       # Save the head of the even list.

        # Reorder the list by rearranging next pointers.
        while even and even.next:
            odd.next = even.next  # Connect current odd to next odd.
            odd = odd.next        # Move odd pointer.
            
            even.next = odd.next  # Connect current even to next even.
            even = even.next     # Move even pointer.
        
        # Append the even list after the odd list.
        odd.next = even_head
        return head