092. Reverse Linked List II

题目链接: https://leetcode.com/problems/reverse-linked-list-ii/description/

题目

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

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

这个题还是蛮有意思的，反转部分链表。

对于链表的问题，根据以往的经验一般都是要建一个dummy node，连上原链表的头结点。

这样的话就算头结点变动了，我们还可以通过dummy->next来获得新链表的头结点。

这道题的要求是只通过一次遍历完成，

就拿题目中的例子来说，变换的是2,3,4这三个点，

那么我们可以先取出2，用front指针指向2，然后当取出3的时候，我们把3加到2的前面，把front指针前移到3，依次类推，到4后停止，

这样我们得到一个新链表4->3->2, front指针指向4。

对于原链表连说，有两个点的位置很重要，需要用指针记录下来，分别是1和5，因为当2,3,4被取走时，原链表就变成了1->5->NULL，

要把新链表插入的时候需要这两个点的位置。1的位置很好找，因为知道m的值，

我们用pre指针记录1的位置，5的位置最后才能记录，当4结点被取走后，5的位置需要记下来，

这样我们就可以把倒置后的那一小段链表加入到原链表中。

代码：

class Solution {
public:
	ListNode *reverseBetween(ListNode *head, int m, int n) {
		ListNode *dummy = new ListNode(-1);
		dummy->next = head;
		ListNode *cur = dummy;
		ListNode *pre = NULL, *front = NULL, *last = NULL;
		for (int i = 1; i < m; ++i) cur = cur->next;
		pre = cur;
		last = cur->next;
		for (int i = m; i <= n; ++i) {
			cur = pre->next;
			pre->next = cur->next;
			cur->next = front;
			front = cur;
		}
		cur = pre->next;
		pre->next = front;
		last->next = cur;
		return dummy->next;
	}
};