Linked List Reverse

Q. How to reverse a linked list.

Good Resource for the basics on linked lists (Linked List 101). 

Possible Solutions: 

• Linear Solution

          Consider the following linked list ( A-->B-->C-->D-->NULL) the expected output is (D-->C-->B-->A-->NULL).

• • With one pointer to the Node 'A' say current we can access the node 'A' and node 'B'. (current-->next). If we point the next node for B to A we get the following (A-->B-->A) however we lose the next node 'C' and also have a loop A-->B-->A information.
  • We can fix this by trying with 2 extra nodes. Node 'prev' points to A and node current points to B. So we can break the node link A-->B and point B-->A ( current points to prev) however we still lose the node C information.
  • Lets us try this approach now with 3 nodes. prev = NULL , current = A, next = B. We continue traversing to the end of the list while updating the 'current' node to point to 'prev' and moving the (prev, current and next nodes by one)

• Recursive Solution 
  • This solution is more intutive. We are essentially trying to traverse till the end of the list and point each node next to its previous node i.e. traverse the list from the TAIL node (D here) D to C to B to A.
  • We use the same logic as above however we now recurseively traverse the linked list till the end of loop and point the current node to the prev node. 
  • In the above example we recurse till current = 'D' and prev is 'C' then point the current D next to C i.e. D-->C.
  • When we come of out the recursive call end noe current is C and prev is B so C-->B, so on till the head node

• Analysis of Solutions 

No.	Solution	Space Complexity	Time Complexity
1.	Linear	O(1)	O(N)
2.	Recursive	O(N) to allocate stack space	O(N)

C++ code

/*
 * LinkedList.h
 *
 *  Created on: Jul 6, 2011
 *  Author: vivekrajumuppalla
 */
#pragma once

#define NULL 0

class Node{
private :
 int m_data;
 Node* m_next;
public:
 Node(int data);
 ~Node();
 int getNodeData();
 Node* getNodeNext();
 void setNextNode(Node* nextNode);
};

Node::Node(int data)
{
 m_data = data;
 m_next = NULL;
}

Node::~Node()
{
 if(NULL != m_next)
 {
  delete m_next;
 }
}

int Node::getNodeData()
{
 return m_data;
}

Node* Node::getNodeNext()
{
 return m_next;
}

void setNextNode(Node* nextNode)
{
 m_next = nextNode;
}

include "listNode.h"
#pragma once

class LinkedList
{
public:
 LinkedList();
 ~LinkedList();
 void recursiveReverse(Node*& headNode);
 void nonRecursiveReverse();

private:
 Node* head;
}

#include "linkedList.h"
void LinkedList::nonRecursiveReverse()
{
        Node* prev = NULL;
 Node* current = head;
 Node* next = NULL;

 while(NULL != current)
 {
  next = current->getNodeNext();
  current->setNextNode(prev);
  prev = current;
  current = next;
 }
 head = prev;
}

// reference needed since we have to update the node not just its pointer 
void LinkedList::recursiveReverse(Node*& headNode) 
{
 if(NULL == headNode || NULL == headNode->getNodeNext())
 {
  tail = headNode;
  return;
 }
 Node* nextNode = headNode->getNodeNext();
 recursiveReverse(nextNode);
 nextNode->setNextNode(headNode);
 headNode->setNextNode(NULL); // This will cause last node to point to NULL
}