-
Notifications
You must be signed in to change notification settings - Fork 0
/
OddEvenLinkedList.cpp
44 lines (41 loc) · 1.2 KB
/
OddEvenLinkedList.cpp
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
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/* Sol 0
* Every time move the odd node to the front.
*/
ListNode* oddEvenList(ListNode* head) {
if(head == nullptr) return head;
ListNode *left_tail = head,*current = head->next;
while(current!= nullptr && current->next != nullptr){
ListNode *temp1 = current->next->next,*temp2 = left_tail->next;
left_tail->next = current->next;
left_tail = current->next;
current->next->next = temp2;
current->next = temp1;
current = temp1;
}
return head;
}
/* Sol 1
* split them into two lists and merge them at last
*/
ListNode* oddEvenList1(ListNode* head){
if(head == nullptr) return head;
ListNode *odd = head,*even = head->next,*even_head = even;
while(even != nullptr && even->next != nullptr){
odd->next = odd->next->next;
even->next = even->next->next;
odd = odd->next;
even = even->next;
}
odd->next = even_head;
return head;
}
};