Odd Even Linked List Python Solution

Tested Python solution for LeetCode 328 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 328, Medium. Topics: Linked List. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 328   # by problem number
lcpy gen -s odd_even_linked_list   # by problem name

​

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

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

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, 10^4]
• -10^6 <= Node.val <= 10^6

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import ListNode


class Solution:
    # Time: O(n) - single pass through list
    # Space: O(1) - only pointer manipulation
    def odd_even_list(self, head: ListNode[int] | None) -> ListNode[int] | None:
        """
        Group odd-indexed nodes followed by even-indexed nodes.

        Example: [1,2,3,4,5] → [1,3,5,2,4]

        Step 1: Separate odd and even chains
        odd:  1 → 3 → 5 → None
        even: 2 → 4 → None

        Step 2: Connect odd tail to even head
        1 → 3 → 5 → 2 → 4 → None
        """
        if not head or not head.next:
            return head

        odd = head
        even: ListNode[int] | None = head.next
        even_head = even

        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next

        odd.next = even_head
        return head

​

Complexity

Time	Space
O(n) - single pass through list	O(1) - only pointer manipulation

​

Tags

Grind.