Road to Google – Part 9: M, N Reversals

Question:

Given a linked list and numbers m and b, return it back only positions m to n in reverse.

Explanation:

So, as you mazy guess, what the question is asking you about is to reverse a specific part of the linked list and return it.

And here are some crucial questions you may need to ask to make things clear.

Will m and n always be within the bounds of the linked list?

Yes, assume 1 <= m <= n <= length of a linked list.

Can we receive m and n values for the whole linked list?

Yes, we can receive m = 1 and n = length of a linked list.

So, in this case, if you get m = 1 and n = 5, you have to return it in the reversed form.

Example 1:

Example 2:

And if you get one linked list like the one that contains 5 or null, just return it as it is.

Thinking time:

Let’s say we’ve got list numbers 1 to 7, and m = 3 and n = 5.

What matters here is that what we need to change here is the portion surrounded by the curly brackets, and the rest are returned as they are.

There are four numbers we need to keep track of. Node 2, for example, doesn’t point at node 3 anymore in the returned form, instead, it points at node 5 – so it is considered as m – 1. And node 3 is m, while node 5 is n. And node 6 can be considered as n + 1. So, it’s important to keep track of both node 2 and 6 that directly touches the nodes that actually flips with each other.

First, we’ve got node 1 as a starting argument, while 3 and 5 as m and n respectively.

Then, we’ll start iterations from the beginning of the node list. Starting from 1, we check if node 1 falls to any of the four numbers. No, then move on to the next.

Then, we hit node 2 and this one matches with one of the four numbers, which is m – 1. So, we get another variable, called start, in which the number 2 is substituted.

Then, we hit node 3 and this one matches with one of the four numbers, which is m. So, we get another variable, called the tail, in which the number 3 is substituted. And from here, let’s also keep track of our steps to reverse the linked list. Since we hit node 3, let’s store the next value, which is 4.

From here, let’s make a new variable: listSoFar which is initialized by null, and also keep track of the reversed version, starting from 3.

Then, update listSoFar to ‘③ -> Null’.

Then, we hit 4. Before updating other parameters, here’s something we need to be aware of. We need to know when to stop reversing – the only way we know it is when the position value became greater than the n value. So, the variable position roles the crucial part.

Then, we hit node 5 and this one matches with one of the four numbers, which is n. And position and current node are updated to 5 while node 6 is stored as the next.

Then, we hit node 6, which is n + 1, meaning it’s the last of the important four numbers.

Since we hit 6, which is bigger than the n, it’s time to reorganize everything. And this is the time we can take advantage of the variables start = 2 and tail = 3. We can direct 2 to the new header 5 and 3 to 6, and substitute it to the listSoFar variable.

Coding solution:

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }

        ListNode start = pre.next;
        ListNode then = start.next;

        for (int i = 0; i < n - m; i++) {
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }

        return dummy.next;
    }
}

class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        Solution solution = new Solution();
        ListNode result = solution.reverseBetween(head, 2, 4);

        while (result != null) {
            System.out.print(result.val + " -> ");
            result = result.next;
        }
    }
}

The code defines a linked list node structure called ListNode with an integer value val and a reference to the next ListNode in the list, called next. It also defines a class called Solution, which includes a method called reverseBetween.

The reverseBetween the method takes in a linked list head, an integer m, and an integer n. The method returns the linked list with the nodes between the mth and nth nodes reversed.

The ListNode the structure is defined as follows:

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

To create a linked list, you can create a new ListNode object and set its val property to the desired value, and its next property to the next node in the list. For example, the following code creates a linked list with values 1, 2, 3, 4, 5:

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

The reverseBetween method begins by checking if the input linked list has no nodes or only one node. If so, the method simply returns the head.

if (head == null || head.next == null) {
    return head;
}

A new ListNode object called dummy is created with a value of 0, and its next pointer is set to the head of the input linked list. A new ListNode object called pre is also created and set to dummy.

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;

A for loop is used to move the pre-pointer to the node before the mth node. Inside the loop, pre is set to its own next node.

for (int i = 1; i < m; i++) {
    pre = pre.next;
}

After the loop, pre points to the node before the mth node. Two new ListNode objects, start and then, are created and set to the mth node and the m+1th node, respectively.

ListNode start = pre.next;
ListNode then = start.next;

A for loop is used to reverse the nodes between the mth and nth nodes. Inside the loop, the next pointers of start and then are updated, and the next pointer of pre is set to then. The then pointer is updated to the next node after start.

for (int i = 0; i < n - m; i++) {
    start.next = then.next;
    then.next = pre.next;
    pre.next = then;
    then = start.next;
}

Finally, the method returns the next pointer of dummy, which points to the head of the updated linked list.

Step-by-step explanation:

Since this part is the most complicated part of the code, here’s an additional step-by-step explanation:

This part of the code is responsible for reversing the linked list from position m to n.

First, it creates two pointers start and then. start points to the node at position m, and then points to the node immediately after start.

Then it runs a loop for n – m iterations since that is the number of nodes that need to be reversed.

In each iteration, it does the following steps:

Sets start.next to be then.next, which means that start will point to the node that comes after then.

Sets then.next to be pre.next, which means that then will now point to the node that pre points to, effectively inserting then before pre.

Sets pre.next to be then, which effectively inserts then between pre and start.

Sets then to be start.next, which means that then now points to the node that comes after start.

After the loop completes, the linked list from position m to n will be reversed, and the method returns the modified linked list.

Here’s an example of how this works on the sample input linked list [1, 2, 3, 4, 5] with m = 2 and n = 4:

start is set to node 2 and then is set to node 3.
The loop runs for 2 iterations:
start.next is set to node 4.
then.next is set to node 2.
pre.next is set to node 3.
then is set to node 4.
Now the linked list is [1, 3, 2, 4, 5].
The method returns the modified linked list.

return dummy.next;