reverse-nodes.cpp

#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;
}