反转指定区间内链表

题目：

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,

return1->4->3->2->5->NULL.

Note:

Given m, n satisfy the following condition:

1 ≤ m ≤ n ≤ length of list.

 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==NULL || head->next==NULL)  return head;
13         
14         ListNode *dummy = new ListNode(0);
15         dummy->next = head;
16         ListNode *prev, *p, *q, *last;
17         //得到m处的结点
18         p = head;
19         for(int i=1;i<m;i++)
20         {p = p->next;}
21         //得到n处的结点
22         q = p;
23         int x = n-m;
24         for(int j=0;j<x;j++)
25         { q = q->next;}
26         //设定last,断开n处结点与后面的结点
27         last = q->next;
28         q->next = NULL;
29         //设定prev,断开m处结点与前面的结点
30         prev = dummy;
31         int y = m;
32         for(int z=1;z<y;z++)
33         { prev = prev->next;}
34         prev->next = NULL;
35         
36         //反转m与n区间间的结点
37         ListNode *tmp1 = p->next;
38         ListNode *tmp2;
39         ListNode *last_new = p;   //lat_new存储反转后的尾结点
40         p->next = NULL;
41         while(tmp1!=NULL)
42         {
43             tmp2 = tmp1->next;
44             tmp1->next = p;
45             p = tmp1;
46             tmp1 = tmp2;
47         }
48         ListNode *fir_new = p;
49         
50         //重新连接
51         prev->next = fir_new;
52         last_new->next = last;
53         
54         return dummy->next;
55     }
56 };