Sponsored
Sponsored
This approach uses two pointers to manage odd and even indexed nodes separately. We maintain separate pointers for the head of the odd and even lists and iterate through the given list. As we go along, we link odd indices to the next odd and even indices to the next even. In the end, we connect the last odd indexed node to the head of the even indexed list.
Time Complexity is O(n) since we traverse the entire list once. Space Complexity is O(1) because we're rearranging pointers without using any extra space for storage.
1#include <iostream>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10class Solution {
11public:
12 ListNode* oddEvenList(ListNode* head) {
13 if (!head || !head->next) return head;
14
15 ListNode* odd = head;
16 ListNode* even = head->next;
17 ListNode* evenHead = even;
18
19 while (even && even->next) {
20 odd->next = even->next;
21 odd = odd->next;
22 even->next = odd->next;
23 even = even->next;
24 }
25 odd->next = evenHead;
26 return head;
27 }
28};The solution starts by checking if the list is empty or has a single node. If true, it returns the list immediately. Two pointers, 'odd' and 'even', are created starting from the first and second nodes, respectively. Another pointer 'evenHead' remembers the start of the even indexed nodes. As the loop progresses, Odd nodes are linked to the next odd nodes and even nodes are linked to the next even nodes. Finally, the last odd node is linked to the even head.
Although not typical due to O(1) space requirement, this problem could conceptually be solved recursively by defining a function that processes the head and its next elements recursively, managing pointers for odd and even segments. As recursion inherently uses extra space on the stack, this isn't space-optimal, thus academically interesting but not compliable with constant space constraints.
Time Complexity remains O(n) for full list traversal. However, Space Complexity rises to O(n) because of the call stack in recursion, unsuitable under given problem constraints for constant space.
1class ListNode:
2 def __init__(self, val=0, next
This Python solution uses a local function 'partition' which recursively treats nodes as alternating odd or even. Despite functional recursion achieving the same odd-even connection, it ruins constant space by occupying stack memory, which might exceed constraints under deep recursion.