Reverse a linked list

Tags: ,

Given a singly linked list, reverse it. For example:

Input:
1->2->3->4->5
Input:
5->4->3->2->1

This problem is never asked standalone in an interview but very important to answer a few of the questions which are commonly asked in Amazon and Facebook interviews like reverse K nodes in a linked list or reverse K alternating nodes.

The idea to reverse a linked list is simple, you take each node, make it point to its previous node, and go to the next node. For each node, we need to maintain three different pointers: current which points to the node we are working on, prev, the node which is immediately previous to the current node and next, the node which is immediately next to the current node.

How do we change the pointers? If we change current.next to point to previous node, we cannot go forward. So, the first thing to secure if that we can move forward, by storing current.next to next.

Now, that we have secured the next pointer, we can change current.next to point to the prev. As we will be moving forward to the next node, the new previous node will be the current node, change prev to current.
The last step, move forward, make current as next.

Here is an example of reversing a linked list
reverse linked list

Keep doing this till we have no nodes remaining in the linked list. What should we return now? current, prev or next? When current is at the null, next would already be null and we cannot return a null value of a linked list which was non-null, right? Only pointer which now points to the last node is prev and should be returned.

There is another confusion and that is how to initialize these three pointers. Which node you will process first? The head. So, the current should be initialized to the head of the linked list. What would be the next pointer of the head in the reversed linked list? It will be null. Initialize prev as null. For next it does not matter, you can choose to initialize it with null or null.

Reverse a linked list implementation

package AlgorithmsAndMe;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class ReverseLinkList {
    public ListNode reverseList(ListNode head) {

        ListNode prev = null;
        ListNode next = head;
        ListNode current = head;

        while(current != null){
            next = current.next;
            current.next = prev;
            prev = current;
            current  = next;
        }

        return prev;
    }
}

The time complexity of reversing a linked list is O(n).