1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* reverseKGroup(ListNode* head, int k) { 12 if(k==1||head==NULL) 13 return head; 14 ListNode *helpleft = new ListNode(0); 15 helpleft->next = head; 16 ListNode *helpright = new ListNode(0); 17 while(head->next!=NULL) 18 head = head->next; 19 head->next = helpright; 20 ListNode *pre=helpleft; 21 head = helpleft->next; 22 ListNode *beh; 23 ListNode *tail; 24 ListNode *ss; 25 ListNode *p = head; 26 int count = 1; 27 while(p!=helpright){ 28 if(count==k){ 29 beh = p->next; 30 tail = p; 31 reverse(pre, beh, head, tail); 32 count = 1; 33 pre = head; 34 ss = pre; 35 head = beh; 36 p = beh; 37 } 38 else{ 39 ss = p; 40 p = p->next; 41 count++; 42 } 43 } 44 ss->next = NULL; 45 delete(helpright); 46 head = helpleft->next; 47 helpleft->next = NULL; 48 delete(helpleft); 49 return head; 50 } 51 52 void reverse(ListNode *pre, ListNode *beh, ListNode *head, ListNode *tail){ 53 ListNode *p = head; 54 ListNode *k = head; 55 while(k!=beh){ 56 k = k->next; 57 p->next = pre->next; 58 pre->next = p; 59 p = k; 60 } 61 head->next = beh; 62 return; 63 } 64 };
就是前后指针卡住要逆置的链表段,原地逆置,再接回去
这里要注意的是,逆置过后,head和tail位置互换了,所以下一组逆置序列中,pre指向的是head