LeetCode 328: Odd Even Linked List
Problem Description
Explanation:
To solve this problem in O(1) extra space complexity and O(n) time complexity, we can reorganize the linked list by separating the odd-indexed nodes from the even-indexed nodes. We can achieve this by iterating through the original linked list and creating two separate lists for odd and even nodes. Finally, we merge these two lists to form the final reordered linked list.
- Initialize two dummy nodes,
oddDummyandevenDummy, to store the heads of the odd and even lists respectively. - Iterate through the original linked list, keeping track of the odd and even nodes separately.
- At the end of the iteration, connect the last odd node to the first even node to form a single reordered linked list.
- Return the head of the reordered linked list.
Time Complexity: O(n)
Space Complexity: O(1)
:
Solutions
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode oddDummy = new ListNode(-1);
ListNode evenDummy = new ListNode(-1);
ListNode oddTail = oddDummy;
ListNode evenTail = evenDummy;
int index = 1;
while (head != null) {
if (index % 2 == 1) {
oddTail.next = head;
oddTail = oddTail.next;
} else {
evenTail.next = head;
evenTail = evenTail.next;
}
head = head.next;
index++;
}
oddTail.next = evenDummy.next;
evenTail.next = null;
return oddDummy.next;
}
}Related LeetCode Problems
Loading editor...