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:
Place the curr node at the head of the list.
Initially, the prev and next pointers won't be referencing any node
i.e prev = fwd = null.
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.
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;
curr.next = prev;
prev = curr;
curr = fwd;
}
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:
Place the curr pointer to the head of Linked List.
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.
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.
Perform the reversing of the sub-list with the three-pointers as we learned above.
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) {
Node curr = head;
Node prev, fwd = null;
if (M == N) {
return head;
}
for(int i=1; i<=m; i++) {
prev = curr;
curr = curr.next;
}
ListNode leftPointCut = prev;
ListNode endNodeOfSubListAfterReversing = curr;
prev = null;
while(curr != null && m<=n) {
fwd = curr.next;
curr.next = prev;
prev = curr;
curr = fwd;
m++;
}
Node startNodeOfSubListAfterReversing = prev;
endNodeOfSubListAfterReversing.next = curr;
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. 🙂
