Reverse a Linked List II: Part 2

This exercise comes from LeetCode, feel free to try it out before reading on!

“You are given a singly linked list and positions m and n. Write a function reverseBetween to reverse the linked list from position m to n.”

Note: 1 ≤ m ≤ n ≤ length of list

Example:
  input = {3, {5, {1, {6, {7, {2, {null}}}}}}}, m = 2, n = 5
  output = {3, {7, {6, {1, {5, {2, {null}}}}}}}
Edge Cases:
// input is null
  input = {} 
  output = null
// m & n are equal
  input = {4, {7, {null}}}, m = 1, n = 1,
  output = same as input
// m is position 1 which means head will need to be reassigned 
  input = {4, {7, {null}}}, m = 1, n = 2
  output = {7, {4, {null}}}

In this article, we solved this problem recursively. If you want to see the iterative approach, check out Hilary’s article here: Reverse a Linked List II: Part 1

This approach consists of two parts: reversing part of the linked list and connecting the ends of the sublists to the original.

Let’s talk about how to reverse an entire linked list first.

In the code above, we traversed the linked list by recursively calling the function with the next node until the next node is null, which is the base case. A variable h is assigned to the last node in the list because the last node needs to become the first node. With each call on the call stack, the head pointer references a different node in the list, in the order we traversed the list. As the calls finish executing and leave the stack, you can imagine it is as if the head pointer is traversing backward. To change the direction of just two nodes (head and head.next), we assigned head.next’s .next property to equal head (Line 6). This is how we made head and head.next point to each other.

However, this created a loop where two nodes were pointing at each other. We dealt with this by reassigning head to point to null (line 7).

Here’s a visual to help clarify what line 6 & 7 do:

Now that we understand how to reverse a linked list, we will walk through the solution and how to connect the reversed sublist to the original list.

Instead of recursively calling the function on the next node, we decremented m and n (Line 9) because the base case is n = 1 (Line 4). When n = 1, we finished traversing and started reversing. We also stored a pointer referencing the node after the nth position (Line 5) because we needed to connect it to the node at the mth position (Line 15). When we reversed the sublist, the mth node became the nth node and vice-versa. Similar to reversing the entire linked list, the head of the reversed sublist was continuously returned (Line 17) until we reached the mth position. Then, we connected the node before the mth position to variable r, the head node of the reversed sublist (Line 21). Finally, we returned head which is the first node of our list to complete the exercise.

Feel free to comment if you have any questions.