Author:hozhangel
Time:2018-08-12 11:45:12
similar problem: 206. Reverse Linked List
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
just like the 206-th ,and add the count
//自己写的代码 在206th 基础上改动 ^^：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* pre = new ListNode(0); pre->next = head; ListNode* pre_new = pre; ListNode* p = pre_new->next; ListNode* q = p->next; int mm = 2; while (q&&mm<=n) { if(mm<=m){ //find the begin node to reverse pre_new=pre_new->next; p = pre_new->next; q = p->next; } else{ //just reverse ListNode* pt = q; p->next = pt->next; pt->next = pre_new->next; pre_new->next = pt; q=p->next; } mm++; } return pre->next; } };
其他值得学习的best-solution: 递归C++-simple-solution-easy-to-understand
class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode* curNode = head; for(int i=0;i<m-1;++i) curNode = curNode->next; reverseBetween(curNode,n-m); return head; } void reverseBetween(ListNode* head, int length){ if(length<=0) return; ListNode* lastNode = head; for(int i=0;i!=length;++i) lastNode = lastNode->next; swap(head->val,lastNode->val); reverseBetween(head->next,length-2); } };
原文：https://www.cnblogs.com/hozhangel/p/9460947.html