算法题（49）：反转链表II

审题：

需要我们对指定范围的链表进行反转，并返回反转后链表的头结点

思路：

方法一：vector法

我们先遍历一次链表，并把数据对应的存在数组中，然后利用数组的reverse方法进行反转数据，最后再遍历一次链表把val值改掉即可

方法二：穿针引线法

我们可以看成某个区间进行整个链表的反转，然后左边界的前一个节点指向右边界，左边界节点指向右边界的下一个节点。

解题：

方法一：

注意：题目给的left和right不是索引，而是第几个数据的意思，所以左迭代器加的是left-1.而右迭代器指向的是最后一个有效数据的下一个位置，所以不用减一了

不过在面试中，我们一般处理链表的时候都不被允许改变val值，而是只能改变链表指向，所以我们有了方法二

方法二：

哨兵节点answer:由于可能会出现整个链表都反转的情况，而我们又需要prv节点，所以我们创建一个哨兵节点，这样就不会出现空指针的访问（nullptr->next）

解题步骤：

1.创建哨兵节点

2.确定反转链表的左右边界指针和prv节点，end节点

3.调用反转函数进行反转

4.进行链表链接

92. 反转链表 II - 力扣（LeetCode）