Reverse a Single Linked List: Iterative Procedure

This is one of the famous interview questions.

Following are two procedures to reverse a single linked list:

• Iterative Procedure
• Recursive Procedure

Iterative Procedure

The following are the sequence of steps to be followed:

• Initially take three pointers: PrevNode, CurrNode, NextNode
• Let CurrNode point to HeaderNode of the list. And let PrevNode and NextNode points to null
• Now iterate through the linked list until CurrNode is null
• In the loop, we need to change NextNode to PrevNode, PrevNode to CurrNode and CurrNode to NextNode

Consider the following linked list that needs to be reversed:

Dry run for the above example:

Taking 3 pointers: PrevNode, CurrNode and NextNode where CurrNode pointing to HeaderNode

After First Iteration:

After the first iteration of the loop, PrevNode points to the node containing element 1 and CurrNode & NextNode points to the node containing element 2. And the node pointed by PrevNode gets unlinked.

After Second Iteration:

After the second iteration of the loop, PrevNode Points to the node containing element 2 and CurrNode & NextNode point to the node containing element 3. And the CurrNode next would be pointing to PrevNode.

By the end of the iteration, PrevNode contains the reverse of the complete list.

Code for the above solution:

Implementation for ListNode, SingleLinkedList are discussed in previous post.

package ds;

public class ReverseSingleListIterative
{
    public ReverseSingleListIterative()
    {
    }

    public ListNode reverseList(ListNode headerNode)
    {
        ListNode prevNode = null;
        ListNode currNode = headerNode;
        ListNode nextNode = null;

        while (currNode != null)
        {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }

        return prevNode;
    }

    public static void main(String[] args)
    {
        /*  Constructing Single Linked List:
            1 -> 2 ->3 -> 4 ->5 */
        SingleLinkedList newList = new SingleLinkedList();
        newList.add(1);
        newList.add(2);
        newList.add(3);
        newList.add(4);
        newList.add(5);
        System.out.println("List before reversal");
        newList.printList();

        ListNode headerNode = newList.getList();
        ReverseSingleListIterative reverseListIter = new ReverseSingleListIterative();
        headerNode = reverseListIter.reverseList(headerNode);
        newList.setList(headerNode);
        System.out.println("List after reversal");
        newList.printList();
    }
}

In the next post we will discuss how to reverse a single linked list using recursive procedure.

Please write comments if you find any of the above algorithms or codes incorrect, or find better ways to solve the same problem.