反轉(zhuǎn)鏈表 II

題目描述：給你單鏈表的頭指針 head 和兩個整數(shù) left 和 right ，其中 left <= right 。請你反轉(zhuǎn)從位置 left 到位置 right 的鏈表節(jié)點(diǎn)，返回 反轉(zhuǎn)后的鏈表 。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/reverse-linked-list-ii/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：利用棧

首先，如果head為null或者head只有一個節(jié)點(diǎn)，直接返回head。

否則， 聲明一個新的頭節(jié)點(diǎn)newHead，聲明一個棧reverseNodes用來放left和right位置之間的節(jié)點(diǎn)（用于逆序），具體處理過程如下：

• 遍歷head中的節(jié)點(diǎn)；

• 將left之前的節(jié)點(diǎn)一次放入新鏈表中；

• 將left和right之間的節(jié)點(diǎn)先放入棧reverseNodes中；

• 用rightNode記錄right位置后節(jié)點(diǎn)的位置；

• 最后，將棧reverseNodes中的節(jié)點(diǎn)一次放入新的鏈表中，然后將rightNode放到新鏈表的最后。

最后，返回newHead.next即為反轉(zhuǎn)后的鏈表。

【每日寄語】 最初所擁有的只是夢想和毫無根據(jù)的自信而已，但是所有的一切都從這里開始。