Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->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.
分析：在纸上画图，弄清楚插入node的过程。
运行时间：4ms
ATTENTION:
为什么return head会报错？
为什么要构建ListNode型的dummy而不是ListNode*型的dummy？（指针的深复制与浅复制）
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* reverseBetween(ListNode* head, int m, int n) { 12 if(!head) return head; 13 if(!head->next || m == n) return head; 14 15 ListNode dummy(-1); 16 dummy.next = head; 17 ListNode* pre_m, *beforeCur = &dummy; 18 ListNode* current = head; 19 20 for(int i = 1; i <= n; i++){ 21 if(i == m) pre_m = beforeCur; 22 23 if(i > m && i <= n){ 24 beforeCur->next = current->next; 25 current->next = pre_m->next; 26 pre_m->next = current; 27 current = beforeCur; 28 } 29 beforeCur = current; 30 current = current->next; 31 } 32 return dummy.next; 33 } 34 };
原文：http://www.cnblogs.com/amazingzoe/p/4510906.html