-
Notifications
You must be signed in to change notification settings - Fork 0
/
Reverse-Nodes-in-k-Group.cpp
145 lines (107 loc) · 2.86 KB
/
Reverse-Nodes-in-k-Group.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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*
* Song Qiang <qiang.song@usc.edu> 2013
*
*/
/*
Given a linked list, reverse the nodes of a linked list k at a time
and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in
the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be
changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
*/
#include <cmath>
#include <vector>
#include <numeric>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <sstream>
#include <limits>
#include <utility>
using namespace std;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (head == NULL || k <= 1) return head;
vector<ListNode*> ptrs(k); // not constant memory
ListNode* h = new ListNode(0);
h->next = head;
ListNode* t = h;
while (true)
{
ListNode* p = t->next;
int i = 0;
for (; i < k && p != NULL; ++i, p = p->next)
ptrs[i] = p;
if (i < k) break;
ptrs.front()->next = ptrs.back()->next;
for (int i = 0; i < k; ++i)
{
t->next = ptrs[k - i - 1];
t = t->next;
}
}
head = h->next;
delete h;
return head;
}
};
class Solution2 {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (head == NULL || k <= 1) return head;
ListNode* r = new ListNode(0);
ListNode* h = r;
while (true) {
ListNode* next_head = head;
int i = 0;
while (i < k && next_head != NULL) {next_head = next_head->next; ++i;}
if (i < k) {
h->next = head;
break;
} else {
h->next = head;
head = head->next;
ListNode* next_h = h->next;
for (int j = 0; j < k - 1; ++j) {
ListNode* tmp = head->next;
head->next = h->next;
h->next = head;
head = tmp;
}
h = next_h;
head = next_head;
}
}
h = r;
r = r->next;
delete h;
return r;
}
};
int
main(int argn, char** argv)
{
Solution s;
}