Reversing a linked list

Copyright Donovan Rebbechi 2001. This tutorial may be distributed freely if this copyright notice is preserved. Changes require authors permission. The code is no-strings attached free software, it may be redistributed, modified, and used.

class List
struct Node
Node(const T& data, Node* next=0):data(data),next(next) {}
Node* next;
T data;

List() : head(0) {}

Node* begin() { return head; }
Node* end() { return 0; }

void reverse()
Node* p = 0; Node* i = begin(); Node* n;
while (i)
n = i->next; //This saves the address of the next node
i->next = p;//// make the next pointer point to previous node
p = i; //// update previous node to point to “current”
i = n;// recall the address of the node after i
head = p;
Node* head;

To reverse the list, we need to traverse the list, and modify the next pointer of each node, so it points to the previous node.

Circular lists: A circular list is a linked list that has the property that the last node in the list contains the address of the first node.


This post is motivated by an interesting article posted above.

Also interesting uses of XOR can be found in the form of XOR swap (no-temp-swap) and XOR linked list (Doubly linked list with a single variable to store both the prev and next pointers)

Following properties of XOR are what makes it very powerful –

X^X=O (Zero) – common sense (a value xor’d with itself is bound to be zero)

X^O = X = identity

X^Y = Y^X  = Reflexivity

X^(Y^Z) = (X^Y)^Z = transitivity


C/C++ – Resources – By Deitel – I have not read this myself 🙂 – Danny Kalev’s blog. Very informative. – C++ Reference

Dr. Dobb’s