Reverse Linked List

Problem

Reverse a linked list from position m to n. Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Challenge

Reverse it in-place and in one-pass.

Solutions

Solution 1

This is similar to reverse-linked-list, we can use the same algorithm to reverse the sub list, but need to remember the node before and after. We can still do it in one-pass. Check the Go solution.

Solution 2

Another solution is to move one node at a time:

If we want to reverse a sub list, after the before node and before the after node, we can imagine this list to be further divided into a done list (d) and a todo list (t):

before -> d_0 -> ... -> d_n -> t_0 -> t_1 -> ... -> t_n -> after

The goal of each iteration is to move the first node of the todo list (t_0) to the beginning of the done list (before d_0 and after before).

The example in the problem description would be finished in 2 iterations:

• 1->2->3>-4->5->NULL: input. 2->3->4 is supposed to be reversed.
  • done: 2; todo: 3->4
• 1->3->2->4->5->NULL: 1st iteration, 3 is pulled before 2.
  • done: 3->2; todo: 4
• 1->4->3->2->5->NULL: 2nd iteration, 4 is pulled before 3.
  • done: 4->3->2; todo: null

Pseudocode:

// Originally only the first node is in the done list.
// This node do not change in the iterations.
doneTail := before.Next
for i := 0; i < right-left; i++ {
    // done list is right after the before node.
    doneHead := before.Next
    // todo list is right after the doneTail node.
    todoHead := doneTail.Next
    // The following 3 actions pull `todoHead` in between `before` and `doneHead`
    before.Next = todoHead
    // Skip the deleted todoHead
    doneTail.Next = todoHead.Next
    // Move todoHead before the done list
    todoHead.Next = doneHead
}