Reverse a singly linked list

If we have a singly linked list like this 1->2->3->4, how can we reverse it so that it becomes 4->3->2->1? The algorithm is pretty simple. We just need to use two extra pointers and traverse the list once. Here is the algorithm in C++:

struct Node
{
  int data; //data
  Node* next; //pointer to next node in the list
};

Node* reverseLinkedList(Node *head)
{
  Node *next = NULL;
  Node *last = NULL;
  while (head != NULL)
  {
    next = head->next;
    head->next = last;
    last = head;
    head = next;
  }
  head = last;

  return head;
}

Our linked list is composed of different Nodes which have a data field and a next field. The next field is a pointer to the next node in the linked list.

Method reverseLinkedList() takes the head node of a list as its argument. It then creates a next pointer to store the next node in the list and a last pointer to store the last node we visit. After that, we traverse the list until our head pointer is null. For each node in the list, we change its next field to the node before it, and we set it as our last visited node. Finally, when we have traversed the whole list, we must set head to last pointer because last is now pointing at the first node in the list while head is pointing to null. After all, we just return head to give access to the beginning of the reversed list.

So, if our list was 1->2->3->4, the reversed list will be 4->3->2->1. As expected, this algorithm takes O(n) time complexity where n is the number of nodes in the list. It also takes O(2) space complexity because we need only 2 additional pointers for any given list.