Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <iostream>
using namespace std;
struct Node {
int val;
Node *next;
};
void print(Node* n) {
do {
cout << n->val << (n->next ? "->" : "");
n = n->next;
} while (n);
cout << endl;
}
Node* reverse(Node* n, int k) {
Node* head = n, *prev = nullptr;
while (n) {
Node* start = n, *end = nullptr, *endn = nullptr;
Node* lprev = nullptr;
// cout << "new loop " << n->val << endl;
for (int i = 0; i < k; i++) {
Node* nn = n->next;
if (i == k-1 || n->next == nullptr) {
end = n;
endn = n->next;
// cout << "endn: " << endn->val << endl;
end->next = lprev;
break;
}
// cout << n->val << " : " << nn->val << endl;
n->next = lprev;
lprev = n;
n = nn;
}
// end->next = start;
if (head == start) {
head = end;
}
if (prev) {
prev->next = end;
}
prev = start;
// print(head);
start->next = endn;
n = endn;
}
return head;
}
Node* newNode(int v, Node* prev) {
Node* n = new Node();
n->val = v;
if (prev)
prev->next = n;
return n;
}
int main() {
Node* n1 = newNode(1, nullptr);
Node* n2 = newNode(2, n1);
Node* n3 = newNode(3, n2);
Node* n4 = newNode(4, n3);
Node* n5 = newNode(5, n4);
Node* n6 = newNode(6, n5);
Node* n7 = newNode(7, n6);
// * n = reverse(n1);
print(n1);
Node *rn = reverse(n1, -1);
print(rn);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment