328. Odd Even Linked List
Odd Even Linked List (LeetCode 328) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.
How to solve Odd Even Linked List
Odd Even Linked List is a Linked List Reordering and Partitioning problem, part of Linked List Manipulation Patterns. Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.
Work towards the solution in these steps:
- Consider how you can traverse the linked list while rearranging nodes in place without using extra memory.
- Think about maintaining two separate pointers: one for nodes at odd positions and another for even positions as you iterate through the list.
- How can you link the odd-indexed nodes together and the even-indexed nodes together during a single pass through the list?
The reference solution runs in O(n) time and O(1) space.
The Odd Even Linked List solution and editorial walks through the full approach with reference code.
Problem statement
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
Topics and companies
Topics: Linked List.
Reported in interviews at Bloomberg, Oracle, Facebook, Google.
How to practise Odd Even Linked List on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Odd Even Linked List in the code editor, or read the Odd Even Linked List editorial for a worked solution with its approach and complexity analysis.
Where Odd Even Linked List sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- Reordering / Partitioning subpattern
- The full DSA patterns sheet
Problems related to Odd Even Linked List
Other problems that use the same Reordering / Partitioning and Linked List Manipulation Patterns techniques:
- Insert Greatest Common Divisors in Linked List — Medium, same subpattern
- Partition List — Medium, same subpattern
- Reorder List — Medium, same subpattern
- Rotate List — Medium, same subpattern
- Swap Nodes in Pairs — Medium, same subpattern
- Add Two Numbers — Medium, same pattern
Odd Even Linked List FAQ
What is the LeetCode number of Odd Even Linked List?
Odd Even Linked List is LeetCode problem 328, rated Medium.
What pattern is used to solve Odd Even Linked List?
Odd Even Linked List is a Linked List Reordering and Partitioning problem. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.
What is the time complexity of Odd Even Linked List?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Odd Even Linked List?
Odd Even Linked List has been reported in interviews at Bloomberg, Oracle, Facebook, Google.