https://oj.leetcode.com/problems/reverse-linked-list-ii/
跟链表按组翻转类似,实现一个能够翻转区间的函数。然后找出这个区间并翻转即可。注意不要丢失链表头。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void Reverse(ListNode *in,ListNode *out,ListNode *&h,ListNode *&t){ ListNode *p=h,*lp=in; while(h->next!=out){ ListNode *q=h->next; h->next=q->next; q->next=p; if (lp!=NULL) { lp->next=q; } p=q; } t=h; h=p; } ListNode *reverseBetween(ListNode *head, int m, int n) { if (head==NULL) return NULL; if (m==n) return head; if (m>n) swap(m,n); ListNode *ll,*l,*lr,*r; r=head; lr=NULL; int count=1; while(r!=NULL){ if (count==m) { ll=lr; l=r; } if (count==n){ break; } lr=r; r=r->next; count++; } ListNode *h=head; if (ll==NULL) { Reverse(ll,r->next,l,r); h=l; } else Reverse(ll,r->next,l,r); return h; } };