Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given1->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.
题目意思：
翻转给定区间[m,n]的链表。
第一个节点m=1。
1<=m<=n<=length。
解题思路：
就我目前学习到的，有用指向指针的指针的，有插入，有逆转的。但是所有方法的核心，都其实是一个算法，就是利用3个指针修改区间内的节点的next值，且要保证已修改的链表是可以被找到的，即可以连入原链表中。
假设有一个链表有1,2,3,4,5,6，6个节点。m=2，n=5。
我们添加一个dummy节点，方便操作第一个节点。
首先让pre指向第m个节点前面那个，cur指向第m个节点，p1指向m的下一个节点，因为p1有可能是NULL，所以当p1不是NULL的时候，p2指向p1的下一个节点。
上图画出了这几个指针指向情况的开始状态和我们希望的终止状态。
在最终状态下，再通过其中方框中的两步就可以我们需要的链表了。
而cur，p1，p2三个指针在区间内向前移动并且将p1的next指向cur的过程则包含在一个for循环内部。如下：
代码如下：
1 class Solution { 2 public: 3 ListNode *reverseBetween(ListNode *head, int m, int n) { 4 ListNode *dummy = new ListNode(0); 5 dummy->next = head; 6 7 ListNode *pre = dummy, *cur = head; 8 for(int i = 1; i < m; i++){ 9 pre = cur; 10 cur = cur->next; 11 } 12 13 ListNode *p1,*p2; 14 if(cur) 15 p1 = cur->next; 16 if(p1) 17 p2 = p1->next; 18 for(int j = m; j < n; j++){ 19 p1->next = cur; 20 cur = p1; 21 p1 = p2; 22 if(p2) p2 = p2->next; 23 } 24 pre->next->next = p1; 25 pre->next = cur; 26 27 return dummy->next; 28 } 29 };
【LeetCode练习题】Reverse Linked List II,布布扣,bubuko.com
【LeetCode练习题】Reverse Linked List II
原文：http://www.cnblogs.com/4everlove/p/3651002.html