leetcode92 反转链表II

思路：
头插法。
实现：
 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution
12 {
13 public:
14     ListNode* reverseBetween(ListNode* head, int left, int right)
15     {
16         if (head == NULL or head->next == NULL or left == right) return head;
17         ListNode* hair = new ListNode(-1);
18         hair->next = head;
19         ListNode* pre = hair;
20         for (int i = 0; i < left - 1; i++)
21         {
22             pre = pre->next;
23         }
24         ListNode* cur = pre->next, *nxt = cur->next;
25         for (int i = 0; i < right-left; i++)
26         {
27             cur->next = nxt->next;
28             nxt->next = pre->next;
29             pre->next = nxt;
30             nxt = cur->next;
31         }
32         return hair->next; 
33     }
34 };