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 (1st position), the second is even (2nd position), and so on.
Example:
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
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
Approach:
- Maintain two pointers:
oddstarting from the first node andevenfrom the second. - Also store a reference to
evenHeadso that we can attach it to the end of the odd list later. - While traversing, link odd nodes together and even nodes together alternately.
- Finally, link the last odd node to the head of the even list.
Time and Space Complexity:
- Time Complexity: O(n) — Each node is visited exactly once.
- Space Complexity: O(1) — In-place manipulation with constant extra space.
var oddEvenList = function(head) {
if (!head || !head.next) return head;
let odd = head;
let even = head.next;
let evenHead = even;
while (even && even.next) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
};
struct ListNode* oddEvenList(struct ListNode* head) {
if (!head || !head->next) return head;
struct ListNode *odd = head, *even = head->next, *evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
class Solution(object):
def oddEvenList(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
if not head or not head.next:
return head
odd, even = head, head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
public class Solution {
public ListNode OddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
