Problems

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.