92. 反转链表 II

 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 {
11 public:
12     ListNode* reverseBetween(ListNode* head, int m, int n) 
13     {
14         //[1,2,3,4,5]
15         int len = n - m + 1;//反转链表的个数
16         ListNode* dummy = new ListNode(-1);//建立虚拟节点
17         dummy->next = head;//虚拟节点的下一个节点为head
18         ListNode* pre = dummy;//pre指针指向dummy
19         //[-1,1,2,3,4,5]
20         while(--m) pre = pre->next;//执行完后，pre指向1
21         ListNode* first = pre->next;//first指向2
22 
23         ListNode* a = first;//备注first
24 
25         ListNode* second = dummy;
26         while(n--) second = second->next;//second走n步到4
27 
28         ListNode* new_head = NULL;//链表反转
29         while(len--)
30         {
31             ListNode* temp = first->next;
32             first->next = new_head;
33             new_head = first;
34             first = temp;
35         }//first指向5
36 
37         pre->next = new_head; //节点值为1的next指针指向new_head
38         a->next = first;//节点值为2的next指针指向5
39 
40         return dummy->next;
41     }
42 };