Reverse LinkedList {Loop implementation}

In the first part I’ve described how to reverse single LinkedList using recursion. Today we will to do the same using one loop.
The structure of linked list will be the same, look to the Node class.
OK, What we should understand? The first implementation used next steps:

  • Go throughout all nodes and set next to null { after these steps we have n-null pointed LinkedLists.}
  • Read from end and change direction of linking.

Current implementation will have different approach and will be implemented using next steps:

  • Create reversed root node.
  • Read next node.
  • Save as next reversed root.
  • Set node to reversed root.
  • Set next node to node; {For making loop}.

Steps are good but example better 🙂, So, we have next list:

First algorithm {recursion implementation} works using two-time loop {recursion} from start to end and from end to start , it’s like recursion working.

So, After first time loop {recursion from start to end} we will have n-lists:

During second time loop {recursion from end to start } we add

elements and will have reversed list

and on the start of second loop {recursion from end to start } we have first element of reversed list and just add new elements to end .

So, what is different to current implementation ?

We have the same list:

and we have just a one loop. So, the main different is changing root element of reversed list. In other words new element will be added to head or better to new element will be added tail of reversed list.

Explanation of above steps:

We have root of reversed list

read first element and add tail {reversedList} as next to first element after it assign first element as tail to {reversedList} for next loop iteration, so we will have

after second iteration will have

and so on.

Code:

Pros:

  • Faster than first implementation because use one loop from start to end
  • Do not use Stack Memory

Cons:

  • Hard to understand for some people {because use diff approach than recursion and stack}

Leave a Reply

Your email address will not be published. Required fields are marked *