[C++] Clean Code


  • 0
    /**
     * To avoid step on your own foot, always save 4 pointers:
     * 1 2 3 ... k,  1 2 3 ... k,  1 2 3 ...
     *           ^   ^         ^   ^
     * Global:
     *     prehead,  head,   kth,  knext
     * or   lhPrev,  lh,      lt,  ltNext (lh : Local-Head, lt: Local-Tail)
     * or   n1Prev,  n1,      nk,  nkNext
     * Whatever make most sense to you.
     * 
     * We also need 2 local for reversing:
     *        prev,  cur
     * 
     */
    
    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            if (k <= 1) return head;
            ListNode dummy(0), *prehead = &dummy, *kth = nullptr;
            dummy.next = head;
            while (kth = findKth(head, k)) {
                ListNode* cur = head, *prev = prehead, *knext = kth->next;
                while (cur != knext) {
                    ListNode* next = cur->next;
                    cur->next = prev;
                    prev = cur;
                    cur = next;
                }
                prehead->next = kth;
                head->next = knext;
                prehead = head;
                head = knext;
            }
            return dummy.next;
        }
    
    private:
        ListNode* findKth(ListNode* node, int k) {
            while (node && --k)
                node = node->next;
            return node;
        }
    };
    

    Use for loop instead of while

    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            if (k <= 1) return head;
            ListNode dummy(0);
            dummy.next = head;
            for (ListNode *n1Prev = &dummy, *n1 = head, *nk, *nkNext;  nk = findKth(n1, k);  n1Prev = n1, n1 = nkNext) {
                nkNext = nk->next;
                for (ListNode* cur = n1, *prev = n1Prev, *next;  cur != nkNext;  prev = cur, cur = next) {
                    next = cur->next;
                    cur->next = prev;
                }
                n1Prev->next = nk;
                n1->next = nkNext;
            }
            return dummy.next;
        }
    
    private:
        ListNode* findKth(ListNode* node, int k) {
            while (node && --k)
                node = node->next;
            return node;
        }
    };
    

Log in to reply
 

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