Tuesday, 29 March 2011

Reverse a linked list–without using extra space



     This is a common interview question asked and i usually confuse this a lot. :) As such any dummy i believe, if they think fast, you can never come with a correct solution.

   Always reversing the list should be done for a single node first and then you should move the pointer.



Consider the below linked list. How would you reverse it with just single iteration.


Linked list



The important things to consider here are, you need to change the head pointer to the last node in the list. The first node’s next should point to NULL. How would you do that?

If you use extra space, you create a new linked list and you remove the first node and append into the new list.

Similar to this way, we need to have a new “result” List pointing to NULL. The iterator we create “current” is pointing to head. At the first run, we do the following,

  • Store the current->next
  • change current->next to result (result will hold the last found head of the reversed list)
  • set result to the current node(the first node is the last found head as of now)
  • move current to the next node.


current = head

result = NULL

result=current                                  next


next = current->next

current->next = result





current = next


Do the above same thing again until current is not NULL. Finally we also handle setting the result to the current which is the last node.

The tricky thing here is, we just need 2 extra copy pointers. next and result. next holds the next node. result always holds the latest head node found.


struct List
    int data;
    List *next;
List* createNode(int data)
    List* n = new List;
    n->data = data;
    n->next = 0;
    return n;
void append(List* head, List* node)
    List *iter = head;
    if(head == 0)
        head = node;
    while(iter->next != 0) iter = iter->next;
    iter->next = node;
    iter->next->next = 0;
List* reverse_list(List* head)
    List* current = head;
    List* result = NULL;
    while(current != NULL)
        List* next = current->next;
        current->next = result;
        result = current;
        current = next;
    return result;
void printList(List* head)
    while(head != NULL) {
        std::cout<<head->data<<" ";
        head = head->next;
void main()
    List* list = createNode(2);
    append(list, createNode(3));
    append(list, createNode(4));
    append(list, createNode(5));
    append(list, createNode(6));
    List* revlist = reverse_list(list);