MediumNo. 0328

Odd Even Linked List — LeetCode 328 Python Solution

Topics
Linked List
On a study list
LeetCode 75
Reading time
3 min

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

Example

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

Python solution

PythonSolution
# 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 head is None:
            return None
        a = head
        b = c = head.next
        while b and b.next:
            a.next = b.next
            a = a.next
            b.next = a.next
            b = b.next
        a.next = c
        return head

Complexity

Time
O(n)where n is the length of the list, and we need to traverse the list once
Space · auxiliary
O(1)

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 328. Odd Even Linked List is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 328. Odd Even Linked List?

LeetCode 328. Odd Even Linked List is rated Medium on LeetCode.

What is the time complexity of LeetCode 328. Odd Even Linked List?

The Python solution on this page runs in O(n), where n is the length of the list, and we need to traverse the list once.

What is the space complexity of LeetCode 328. Odd Even Linked List?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 328. Odd Even Linked List cover?

LeetCode 328. Odd Even Linked List is tagged Linked List on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.