反转链表 II

题目描述：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：利用栈

首先，如果head为null或者head只有一个节点，直接返回head。

否则， 声明一个新的头节点newHead，声明一个栈reverseNodes用来放left和right位置之间的节点（用于逆序），具体处理过程如下：

• 遍历head中的节点；

• 将left之前的节点一次放入新链表中；

• 将left和right之间的节点先放入栈reverseNodes中；

• 用rightNode记录right位置后节点的位置；

• 最后，将栈reverseNodes中的节点一次放入新的链表中，然后将rightNode放到新链表的最后。

最后，返回newHead.next即为反转后的链表。

【每日寄语】 最初所拥有的只是梦想和毫无根据的自信而已，但是所有的一切都从这里开始。