18 lines concise and easy understand C++ solution iterative and recursion


  • 0
    A

    Iterative version:

    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            if(!head || k == 1) return head;
            ListNode newHead(0);
            ListNode* pre = &newHead,* it = pre, * cur;
            pre->next = head;
            int len = 0;
            while(it = it->next) len++;
            while(len >= k){
                cur = pre->next;
                for(int i = 1; i < k; i++){
                    ListNode* mov = cur->next;
                    cur->next = mov->next;
                    mov->next = pre->next;
                    pre->next = mov;
                }
                len -= k;
                pre = cur;
            }
            return newHead.next;
        }
    

    };

    Recursive version:

    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            int len = k;
            ListNode* it = head;
            while(it && len--) it = it->next;
            if(len > 0) return head;
            else{
                len = k;
                ListNode newHead(0);
                ListNode* pre = &newHead;
                ListNode* cur = pre->next = head;
                while(--len){
                    ListNode* mov = cur->next;
                    cur->next = mov->next;
                    mov->next = pre->next;
                    pre->next = mov;
                }
                cur->next = reverseKGroup(cur->next, k);
                return newHead.next;
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.