Is there any better C++ code?


  • 4
    S

    Thanks for luming.zhang.75 give the excellent code. I try to change a little.

     /**********************
     * author : s2003zy
     * weibo  : weibo.com/songzy982
     * blog   : s2003zy.com
     **********************/
    class Solution {
    public:
        ListNode *reverseKGroup(ListNode *head, int k) {
            if (!head || k == 1) return head;
            int listLen = 0;
            ListNode preHead(0);
            preHead.next = head;
            ListNode* cur = &preHead, *pre = &preHead, *next = NULL;
            while (cur = cur -> next) listLen++;
            while (listLen >= k) {
                cur = pre -> next;
                next = cur -> next;
                for (int i = 0; i < k - 1; i++) {
                    cur -> next = next -> next;
                    next -> next = pre -> next;
                    pre -> next = next;
                    next = cur -> next;
                }
                pre = cur;
                listLen -= k;
            }
            return preHead.next;
        }
    

    };


  • 0

    Thanks for sharing with your solution! Personally, I think yours are the best solution.

    Here is the JAVA translation:

    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
    
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, curr = head, next = head.next;
    
        int len = 0;
        while(curr != null) {
            curr = curr.next;
            len++;
        }
       
        while(len >= k) {
            curr = prev.next;
            next = curr.next;
            for(int i = 0; i < k - 1; i++) {
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
                next = curr.next;
            }
            prev = curr;
            len -= k;
        }
        
        return dummy.next;
    }

  • 0
    Y
    This post is deleted!

  • 0
    N

    What would be time complexity ?


  • 0
    X

    Thanks for your code. I think using the second rank pointers may be a better choice.

    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            ListNode **pp1 = &head, **pp2 = &(head->next), *tmp;
            int num = 0;
            for(tmp=head; tmp; num++) tmp=tmp->next;
            while(num>=k) {
                for(int i=1; i<k; i++) {
                    tmp = *pp2;
                    *pp2 = tmp->next;
                    tmp->next = *pp1;
                    *pp1 = tmp;
                }
                pp1 = pp2;
                pp2 = &((*pp2)->next);
                num -= k;
            }
            return head;
        }
    };
    

Log in to reply
 

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