Reverse a Linked List II: Part 1

Problem

This week, Malinda Lin and I decided to work together on a linked list problem from LeetCode in Javascript, and then explain it to some of our peers. Here is the problem:

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 in one pass.

Note: 1 ≤ m ≤ n ≤ length of list

For example, if we are given the following inputs:

head = {val: 1, next: {val: 2, next: {val: 3, next: {val: 4, next: {val: 5, next: {val: 6, next: null}}}}}}
m = 2
n = 5

Since we are reversing the linked list only from position m to position n, we expect our sample output to look like:

head = {val: 1, next: {val: 5, next: {val: 4, next: {val: 3, next: {val: 2, next: {val: 6, next: null}}}}}}

Here’s a better visual:

            m           n
            |-----------|
Input:  1 → 2 → 3 → 4 → 5 → 6 → null
            |-----------|
Output: 1 → 5 → 4 → 3 → 2 → 6 → null

Review: Linked Lists

A linked list is a dynamic data structure which uses noncontiguous memory storage to organize items sequentially by using pointers. (Picture the clues in a scavenger hunt.) Linked lists can be singly linked (unidirectional) or doubly linked (bidirectional). Today, we are dealing with a singly linked list.

• Each item in a linked list is called a node, and the first node in a linked list is called the head
• Each node contains 1) one value and 2) one pointer to thenext node, and the last node in a linked list has a next pointer that points to NULL
• Most languages, including Javascript, don’t provide a linked list implementation, but we can assume for this problem that each node is represented as a class with two properties — value and next

class Node {
   constructor(val, next = null) {
      this.val = val;
      this.next = next;
   }
}

• The key to working with linked lists is to update the next pointer, whether the operation is deletion, insertion, or reversal
• Always pay attention to edge cases here, as you will likely need to make special accommodations when you are dealing with the head or the last node
• Due to its noncontiguous memory use, iterating through a linked list could, at worst, require O(n) time, where n = number of items in the linked list

Solution 1 — Iterative

Approach

Let’s break this down into subproblems.

Subproblem 1: Reversing a linked list

first iteration

second iteration

last iteration

If we wanted to reverse an entire linked list from beginning to end, we would need to iterate through the linked list, tracking both the current node, as well as the node immediately before it (prev). As we iterate, we would change the next pointer of each node so that it points instead to the previous node, effectively swapping next and prev for every node. We would start with the head and convert it to the last node, then convert the 2nd node to the 2nd-to-last node, and so on until we have traversed the entire sequence.

Note that the order of operations is important here, as we would need to save the contents of curr.next (the next pointer in our current node) in a temporary variable before setting curr.next equal to prev. Otherwise, we would end up stepping back into the previous node when we try to iterate forward.

At the end of the reversal process, we arrive with the prev pointer on the new head of the linked list.

function reverse (head) {
  let curr = head;
  let prev;
  let temp;

  while (curr) {
    temp = curr.next;    // save before we overwrite curr.next!
    curr.next = prev;    // reverse the pointer

    // step forward in the list
    prev = curr;
    curr = temp;
  }

  return prev;
}

Subproblem 2: Re-linking the sublist to the rest of the linked list

Our complete linked list reversal above does a lot of the heavy lifting needed in this problem, but what happens to the nodes directly preceding and directly following the sublist between m and n? How do those stay connected to our reversed sublist?

In order to connect them, we need to use two additional pointers, which we call beforeM and newSubTail. The beforeM pointer is on the preceding node and is responsible connecting to the new start of the sublist — this node stays in place and is not reversed.

Again, order of operations matters here as we must make this change as soon as the reversal process is complete, so that we would still have the start of the sublist tracked by one of our pointers as prev (as we tried to step forward through the end of our sublist and curr goes out of bounds).

One edge case we need to be mindful of is one in which the sublist has no preceding nodes, or in other words, the sublist begins at the head. If this is the case, the new start of the sublist would become the new head.

After the reversal takes place, the newSubTail pointer is on the last node of the sublist and is responsible for connecting to the node directly following the changing sublist. Note that newSubTail starts as the “sub-head” of the sublist and becomes the sub-tail due to the reversal process.

Tying it all together, we can tackle the problem like this:

1. Create pointers curr and prev and set curr to the head so we can start traversing the linked list from there. Traverse the linked list (moving prev and curr at each step of the way) until we get to our sublist starting point at m.
2. Create and set pointers beforeM and newSubTail, which will end up where we need them to be to re-link to the rest of the linked list (right before the sublist starts and right before the sublist ends) after reversal is complete.
3. Do the reversal! But only up until n.
4. Update the next properties on beforeM and newSubTail to reconnect back to home base. Note that if the sublist began at the head, then the new start of the sublist becomes the new head.
5. Review the code and address any other edge cases (such as when the input received includes a falsyhead, or if the sublist starts and ends on the same position — requiring no reversal at all).

Code

You can also find our solutions on our Github repo.

Note that in the above code, we iterated through the linked list by decrementing m and/or n each time in a while loop. It is also possible to increment using a for loop where m and/or n are part of the loop boundaries (ex: for (let i = 1; i < m; i++) and for (let i = m; i < n; i++)) or by using a counter that increments on each move.

Complexity Analysis

Time complexity is O(n) where n = number of nodes in the linked list
We process each of the nodes at most one time (at most because we don’t process nodes after n)

Space complexity is O(1) since we update the linked list in place by adjusting pointers, and we only use O(1) additional memory for the pointers we create.

Please see part 2 for a recursive approach to solving this problem.