Reversing a singly linked list in a single pass

Today I’d like to give codes and solution to reverse a singly linked list in a single pass and not using superfluous storage.

Off course there is a solution if you duplicate list, put all values into a vector or array, and other not efficient ways to accomplish this task. Recursive solutions could also be proposed. But iterative solution is the best way to solve this problem. Because if you use recursive method, there will be superfluous, and not necessary method calls and extra stack storage will be used for each local variables, and it won’t be best shot because if number of nodes in linked list is too much then you’ll probably exhaust your stack memory.

So I’ll describe my solution briefly.

I’ll keep two more pointers while iterating.

First pointer holds the previous node’s address, whilst second pointer will hold next node’s address. Nomenclature will be: prev for previous node’s address, curr for current node’s address, next for the next node’s address.

Simple demonstration is given in below at Image-1:

Image – 1: Initial Condition

In first step, we’ll store previous and next nodes’ addresses and update curr node’s next address to point prev node. In image-2 shows the procedure.

Image – 2: reverse operation steps.

First two step and last step is drawn in image-2. We have wrong next just for the first node (node value 70 in example). But it can easily be updated after the while loop with single instruction.

Full code is given below:

#include <iostream>

// Hayati Gonultas
// copy left
// iclykofte.com

using namespace std;

struct Node {
    int val;
    struct Node* next;
};

Node* head;

void add_node_head(int val)
{
    Node* n = new Node;
    n->val = val;

    if (head == NULL) {
        head = n;
        n->next = NULL;
    }
    else {
        n->next = head;
        head = n;
    }
}

void add_node_tail(int val)
{
    Node* node = new Node;
    node->val = val;
    node->next = NULL;

    if (head == NULL) {
        head = node;
    }
    else {
        Node* n = head;
        while ( n != NULL ) {
            n = n->next;
        }

        n-> next = node;
    }
}

void display(Node* start)
{
    for (Node* n = start; n != NULL; n = n->next) {
        cout << n->val << endl;
    }
}

void reverse_list(Node* start)
{
    // empty list just return
    if (start == NULL)
        return;

    // list with only one item just return as is
    if (start->next == NULL)
        return;

    // pointers to keep backups of old pointer values
    Node* prev = start;
    Node* curr = start->next;
    Node* next = NULL;

    if (curr->next)
        next = start->next->next;

    while(curr != NULL) {
        // update pointers to be in reverse order
        curr->next = prev;

        // update head
        head = curr;

        // update iteration
        prev = curr;
        curr = next;
        if (next != NULL)
            next = next->next;
    }

    // sign start node to be end node
    start->next = NULL;
}


int main() {

    add_node_head(10);
    add_node_head(20);
    add_node_head(30);
    add_node_head(40);
    add_node_head(50);
    add_node_head(60);
    add_node_head(70);

    // this will output 70, 60, 50, 40, 30, 20, 10
    cout << "original list:" << endl;
    display(head);

    reverse_list(head);

    // this will output 10, 20, 30, 40, 50, 60, 70
    cout << "reversed list:" << endl;
    display(head);

    return 0;
}