Reverse a linked list–without using extra space

 

Introduction

     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.

 

Concept

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

result=current

 

                                                        current=next

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.

Code

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;

        head->next=0;

        return;

    }

    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);

    printList(revlist);

}