首页 > 代码库 > Leetcode: Reverse Nodes in k-Group

Leetcode: Reverse Nodes in k-Group

链表的倒转,

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
   ListNode* reverseKGroup(ListNode* head, int k){
    if(!head || !head->next || k <= 1)
        return head;
    ListNode* pFirst = head;
    ListNode* pBefore = NULL;
    ListNode* pKth = pFirst;
    while(1) {
        int cnt = k -1;
        while(cnt && pKth){
            pKth = pKth->next;
            cnt--;
        }
        if(cnt > 0 || pKth == NULL) break;
        reverse(pBefore,pFirst,pKth);
        if(pBefore == NULL)
            head = pFirst;
        pBefore = pKth;
        pFirst = pKth->next;
        pKth = pFirst;
    }
    return head;
   }
   void reverse(ListNode* pBefore, ListNode*& pFirst, ListNode*& pKth){
    ListNode* p = pFirst;
    while(p != pKth) {
        ListNode* tmp = p->next;
        p->next = pKth->next;
        pKth->next = p;
        p = tmp;
    }
    ListNode* tmp = pFirst;
    pFirst = pKth;
    pKth = tmp;
      if(pBefore)
        pBefore->next = pFirst;
   }
};


Leetcode: Reverse Nodes in k-Group