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
- done:
1->3->2->4->5->NULL
: 1st iteration,3
is pulled before2
.- done:
3->2
; todo:4
- done:
1->4->3->2->5->NULL
: 2nd iteration,4
is pulled before3
.- done:
4->3->2
; todo:null
- done:
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
}