Reverse a Singly Linked List

In previous post, we saw the methods to get the data based on index and get the index of data in linked list.In this post, we will see the algorithm to reverse a singly linked list and implement in JAVA.

Examples:

1. Original linked list : 1->2->3->4->5->NULL

Reversed linked list : 5->4->3->2->1->NULL

2. Original linked list : 1->NULL

Reversed linked list : 1->NULL

3. Original linked list : NULL

Reversed linked list : NULL

We can reverse a singly linked list by reversing the pointers in reverse direction. This is very common algorithm to reverse the singly linked list.Apart from this, we will see the other algorithm where we will reverse a singly linked list using Stack.

By reversing the pointers : See the below algorithm and their execution process.

Algorithm:

  1. Declare 3 node variables , current,  previous, next and initialize current=root node.
  2. Repeat steps 3, 4 and 5 till current != null
  3. next= next node of current node
  4. next node of current node = previous . Here, we are reversing the pointer.
  5. current=next
  6. assign the root node as previous , root=previous.

Execution process:

Reverse using Stack  : Now, we will see the algorithm to reverse a singly linked list using Stack.See the below steps and execution process.

Algorithm:

Put the nodes of linked list starting from root node to Stack.

  1. Create an object of Stack of Node<T> . Create node variable,  current and assign the root node.
  2. Repeat steps 3 and 4 till current node is not null.
  3. push the current node to stack. stack.push(current).
  4. assign current as next node of current node. current=next node of current node.

Now, Stack has all the nodes where root node at bottom and rear node at top.Clear the linked list and pop the nodes from stack and update the pointers.

  1. clear the linked list by updating the reference of root as null. root=null
  2. Pop the top node from stack and assign it to root. root=stack.pop().
  3. Create 2 node variables, previous and current and assign as root node.
  4. Repeat steps 5, 6 and 7 till stack is not empty.
  5. pop the node from stack and assign to current. current=stack.pop().
  6. Set next node of previous node as current.
  7. previous=current
  8. Finally, set next node of previous node as NULL. Here previous will be the last node in linked list.

Execution process:

Now, we will have these two algorithm implementation in JAVA. [Try Yourself]

 

 

Output:

Original List: [Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0]]

After reversing List: [Item [itemId=103, itemName=IPhone-XX, price=1000.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=101, itemName=IPhone-5S, price=200.0]]

After reversing using stack List: [Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0]]

 

 

Hope you like this post. Please leave your comments/suggestions.

In next post, we will see the implementation to get the middle of a Singly Linked List.

You may like –

Top