思路:
头插法。
实现:
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 };