-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path328.odd-even-linked-list.cpp
More file actions
64 lines (58 loc) · 1.54 KB
/
328.odd-even-linked-list.cpp
File metadata and controls
64 lines (58 loc) · 1.54 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Tag: Linked List
// Time: O(N)
// Space: O(1)
// Ref: -
// Note: -
// 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
//
//
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head) {
return nullptr;
}
ListNode *odd = head;
ListNode *even = head->next;
ListNode *even_head = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = even_head;
return head;
}
};