We learned in the Basics of Linked Lists that traversal in a Singly Linked list is uni-directional. This means we can only move forward from one node to the other as we always only maintain a pointer to only the next node in the list. After moving, to go back to the previous node we won't have any reference information in our current Node data structure. Our only way of traversing backward is to reverse the linked list.

Compared to Singly Linked List, traversing backward would have been easier if we had a Doubly Linked List. As the DLLNode maintains gives us two pointers, one pointing to the previous node and one pointing to the next node in the list.

Reverse a Linked List (Iteratively)

To reverse a linked list iteratively and in place, we need 3 new pointers: Previous (prev), Current (curr), and Forward (fwd) pointer.

Algorithm:

1. Place the curr node at the head of the list.

2. Initially, the prev and next pointers won't be referencing any node
   i.e prev = fwd = null.

3. Now, iteratively:
    3.1. Place the fwd pointer on the node just after the Current Pointer (curr).
    3.2. Make the curr node's next pointer (curr.next) to the prev pointer.
      Basically, starting the reversal process for curr node.
    3.3. Because in step 3.1, we had already placed the fwd pointer ahead of curr.
      So, now we can move the curr pointer to fwd, which is the new node we need to process for reversing.
    3.4. Keep iterating until curr reaches the end of the list and there are no more nodes to be reversed.

4. Return the prev pointer reference. Because prev will now be pointing to the last node of the original list, and it is now the head of the newly reversed linked list.

Here's a visual representation of the linked list reversal algorithm we discussed above:

Visual flow for reversing a Singly Linked List

Code:

public Node reverse(ListNode head) {
    Node curr = head;
    Node prev, fwd = null;

    while (curr != null) {
      fwd = curr.next; // set the forward pointer just after the current node
      curr.next = prev; // make the current node's next pointer to previous node
      prev = curr; // move prev pointer to current's position
      curr = fwd; // move curr pointer forward's position
    }

    return prev;
}

Code to reverse a linked list in Java

Once you feel comfortable with iteratively reversing a linked list, we can move on to some variations and learn how we can apply this approach to other problems.

Reverse a Sub-List

Now, our task is to reverse only a part of the list. Assume we are given this list:
1 --> 2 --> 3 --> 4 --> 5 --> 6
Additionally, we are given indexes M and N that indicate the positions in the list between which we reverse the nodes. So if we are given M = 2, N = 5, the final result of reversing the sublist should be:
1 --> 5 --> 4 --> 3 --> 2 --> 6

Algorithm:

1. Place the curr pointer to the head of Linked List.

2. As we want to reverse only a part of the list, we need to bring the curr pointer to the Mth node. We also have a prev pointer following the curr, as it will be used to join/stitch the list again after we do the reversing.

3. Now prev pointer will be our left stitching point and curr pointer will point to the node which will be now the new end node of the sub-list.

4. Perform the reversing of the sub-list with the three-pointers as we learned above.

5. Stitch the left and right sides of the list with the new start & end node of the sub-list.

Code:

Code to reverse a sub-list in Java

public Node reverseSubList(Node head, int M, int N) {
    // assume M & N are in valid range of length of list
    Node curr = head;
    Node prev, fwd = null;

    // if M & N point to the same node, there is nothing to reverse.
    if (M == N) {
        return head;
    }

    // move curr pointer to a point where we start reversing nodes
    for(int i=1; i<=m; i++) {
        prev = curr;
        curr = curr.next;
    }

    ListNode leftPointCut = prev;
    ListNode endNodeOfSubListAfterReversing = curr;

    // reset prev
    prev = null;

    // This while loop is exactly was we saw above when reversing a Linked list with 3 pointers: prev, curr and fwd
    // We just need an additional condition to only reverse the nodes in subList
    while(curr != null && m<=n) {
        fwd = curr.next;
        curr.next = prev;
        prev = curr;
        curr = fwd;  
        m++;
    }

    Node startNodeOfSubListAfterReversing = prev;

    // stitch the right point cut
    endNodeOfSubListAfterReversing.next = curr;

    // stitch the left point cut, to the new head of subList which will be pointed by prev i.e startNodeOfSubListAfterReversing
    leftPointCut.next = startNodeOfSubListAfterReversing;

    return head;
 }

Applying the Pattern...

You can apply the reversing of the linked list pattern to the following problems on Leetcode:

1.1. Add Two Numbers - First practice this problem
1.2. Add Two Numbers II - Then look at this problem and think about how you can apply the reversal pattern here

2.1. Reverse Nodes in k-Group - Conceptually it is the same as the problems we discussed in this post. The only tricky part is how you manage the pointers to perform the stitching of the reversed sublists.
2.2 Reverse Nodes in Alternate k-Groups - I didn't find this on Leetcode, but the only change in this problem is you reverse every alternate k-group of nodes.

Once you solve the above practice problems, you should be pretty comfortable with traversing around a singly linked list.

While I know most companies don't test you on Linked List questions these days. It is an important first step in your coding interview prep to make yourself comfortable handling pointers and references. It also provides you with a way of thinking and approaching any twisted Linked List question in your coding interviews.

Upcoming next is another pattern on Linked List called the Slow & Fast Pointer approach. 🙂