Reversing a singly linked list in O(n) time with a single extra node reference.

rev.cpp

#include <vector>
#include <ostream>
#include <iostream>
#include <string>
#include <cstdlib>

struct Node {
    Node *next;
    int   val;
    Node(Node *n, int v) : next(n), val(v) { }
};

std::ostream&
operator << (std::ostream &o, Node &n)
{
    o << n.val;
    if (n.next)
        o << ", " << *(n.next);
    return o;
}

Node*
fromVec(std::vector<int> &vec)
{
    int siz = vec.size();
    if (! siz)
        return nullptr;
    else {
        Node *head = new Node(nullptr, vec[0]);
        Node *puthere = head;
        for (int i=1; i<siz; i++) {
            puthere->next = new Node(nullptr, vec[i]);
            puthere = puthere->next;
        }
        return head;
    }
}

void
freeList(Node *head)
{
    while (head) {
        Node *next = head->next;
        delete head;
        head = next;
    }
}

#define swap(left, right) \
    do { \
        (left)  = reinterpret_cast<Node*>(reinterpret_cast<intptr_t>(left) \
                                         ^reinterpret_cast<intptr_t>(right)); \
        (right) = reinterpret_cast<Node*>(reinterpret_cast<intptr_t>(left) \
                                         ^reinterpret_cast<intptr_t>(right)); \
        (left)  = reinterpret_cast<Node*>(reinterpret_cast<intptr_t>(left) \
                                         ^reinterpret_cast<intptr_t>(right)); \
    } while (0)

void
reverseList(Node **their_head)
{
    if (! *their_head)
        return;
    else {
        Node *prev = nullptr;
        while (1) {
            if ((*their_head)->next) {
                swap(prev, ((*their_head)->next));
                swap(prev, *their_head);
            } else {
                (*their_head)->next = prev;
                return;
            }
        }
    }
}

int
main(int argc, char **argv)
{
    int howmany;
    if (argc == 1)
        howmany = 9;
    else if (argc == 2)
        howmany = atoi(argv[1]);
    else {
        std::cerr << "Usage: " << argv[0] << " [howmany]" << std::endl;
        return 2;
    }

    std::vector<int> vec;
    for (int i=1; i<=howmany; i++)
        vec.push_back(i * 11);

    Node *lst = fromVec(vec);
    std::cout << *lst << std::endl;

    reverseList(& lst);
    std::cout << *lst << std::endl;

    return 0;
}