[LeetCode] 92. Reverse Linked List II

轉自LeetCode

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

<Solution>

Reverse Linked List 的衍生題，這次可以指定範圍來 reverse

解題想法如下(參考資料)

• 用個 dummy head，dummy->next 永遠指向最後答案的 head

• 找到要反轉起始位置的前一個 node，用指針 prv 記錄下來

• 要反轉起始位置，就是反轉後的最後一個 node，也用指針 reverseTail 記錄下來

• 把要反轉的 node 一個一個拿出去，並用 reverse order 的方式組合在一起，這之間都用指針 reverseHead 一直記錄 reverse linked list 的頭

• 將  reverseTail->next  指向 prv->next，然後再將 prv->next 指向 reverseHead

• 回傳 dummy->next

舉例

1  ->  2  ->  3  ->  4  ->  5  ->  6，m = 3, n = 5

則
initial:
                 prv
dummy  ->  1  ->  2  ->  3  ->  4  ->  5  ->  6

round 1:
                 prv
dummy  ->  1  ->  2   ->  4  ->  5  ->  6

           3
reverseHead，reverseTail

round 2:
                 prv
dummy  ->  1  ->  2  ->  5  ->  6

        4  ->  3
reverseHead  reverseTail

round 3:
                 prv
dummy  ->  1  ->  2  ->  6

        5  ->  4  ->  3
reverseHead       reverseTail

final:
                 prv
dummy  ->  1  ->  2  ->  5  ->  4  ->  3  ->  6
                    reverseHead    reverseTail

code 如下