In this guide, you will get 328. Odd Even Linked List LeetCode Solution with the best time and space complexity. The solution to Odd Even Linked List problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
328. Odd Even Linked List LeetCode Solution in C++
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode oddHead(0);
ListNode evenHead(0);
ListNode* odd = &oddHead;
ListNode* even = &evenHead;
for (int isOdd = 0; head; head = head->next)
if (isOdd ^= 1) {
odd->next = head;
odd = odd->next;
} else {
even->next = head;
even = even->next;
}
odd->next = evenHead.next;
even->next = nullptr;
return oddHead.next;
}
}; /* code provided by PROGIEZ */
328. Odd Even Linked List LeetCode Solution in Java
class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode oddHead = new ListNode(0);
ListNode evenHead = new ListNode(0);
ListNode odd = oddHead;
ListNode even = evenHead;
for (boolean isOdd = true; head != null; head = head.next, isOdd = !isOdd)
if (isOdd) {
odd.next = head;
odd = odd.next;
} else {
even.next = head;
even = even.next;
}
odd.next = evenHead.next;
even.next = null;
return oddHead.next;
}
} // code provided by PROGIEZ
328. Odd Even Linked List LeetCode Solution in Python
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
oddHead = ListNode(0)
evenHead = ListNode(0)
odd = oddHead
even = evenHead
isOdd = True
while head:
if isOdd:
odd.next = head
odd = head
else:
even.next = head
even = head
head = head.next
isOdd = not isOdd
even.next = None
odd.next = evenHead.next
return oddHead.next # code by PROGIEZ
