How do you solve Odd Even Linked List on LeetCode?

Odd Even Linked List (LeetCode #328) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The problem requires maintaining the relative order of nodes.

What is the brute force solution for Odd Even Linked List?

The brute force approach for Odd Even Linked List is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we can traverse the linked list and store the values of the nodes in two separate lists: one for odd indexed nodes and another for even indexed nodes. After that, we can concatenate these two lists to form the final reordered list. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Odd Even Linked List?

Odd Even Linked List uses the following concepts: Linked List. The recommended patterns to study are: Two Pointers, Linked List.

What are the interview tips for Odd Even Linked List?

Always clarify the problem requirements and constraints. Think about edge cases before diving into coding. Explain your thought process as you code to demonstrate your understanding.

What are common mistakes when solving Odd Even Linked List?

Not handling edge cases like an empty list or a single node. Confusing the indices of odd and even nodes.

#328

Odd Even Linked List

Medium

Linked ListTwo PointersLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

In the optimal solution, we can rearrange the nodes in a single pass without using extra space for lists. We maintain two pointers for odd and even nodes and connect them directly, ensuring we preserve the original order.

⚙️

Algorithm

3 steps

1Step 1: Initialize two pointers, one for the odd indexed nodes and one for the even indexed nodes.
2Step 2: Traverse the linked list, linking odd indexed nodes together and even indexed nodes together.
3Step 3: Connect the last odd node to the head of the even indexed nodes.

solution.py18 lines

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def oddEvenList(head):
7    if not head or not head.next:
8        return head
9    odd = head
10    even = head.next
11    evenHead = even
12    while even and even.next:
13        odd.next = even.next
14        odd = odd.next
15        even.next = odd.next
16        even = even.next
17    odd.next = evenHead
18    return head

ℹ

Complexity note: The time complexity is O(n) because we traverse the linked list only once. The space complexity is O(1) as we are not using any extra space that grows with input size.

1The problem requires maintaining the relative order of nodes.
2We can use two pointers to efficiently rearrange the nodes in a single pass.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.