92. 反转链表 II
难度中等 给你单链表的头指针
head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]
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 public: 13 ListNode* reverseList(ListNode* head, ListNode* end) { 14 //[head,end) 15 if(head == nullptr || head->next == nullptr) return head; 16 ListNode* pre = nullptr; 17 ListNode* cur = head; 18 ListNode* next = head; 19 while(cur != end) { 20 next = cur->next; 21 cur->next = pre; 22 pre = cur; 23 cur = next; 24 } 25 return pre; 26 } 27 ListNode* reverseBetween(ListNode* head, int left, int right) { 28 if(head == nullptr || head->next == nullptr) return head; 29 if (left == right) return head; 30 // 哨兵 31 ListNode* fake = new ListNode(0); 32 fake->next = head; 33 ListNode* cur = fake; 34 ListNode* left_node = head; 35 ListNode* right_node = head; 36 37 //遍历找到左节点跟右节点 38 int cnt = 0; 39 while(cur!=nullptr) { 40 if(cnt==left-1) { 41 left_node = cur; 42 } 43 if (cnt == right) { 44 right_node = cur; 45 } 46 cur = cur->next; 47 cnt++; 48 } 49 ListNode* right_node_next = right_node->next; 50 left_node->next = reverseList(left_node->next,right_node->next); 51 ListNode* temp = fake; 52 while(temp->next!=nullptr) { 53 temp = temp->next; 54 } 55 temp->next = right_node_next; 56 return fake->next; 57 } 58 };