24ms Easy C++ Iterative Solution with Explanations


  • 13

    Well, since the head pointer may also be modified, we create a new_head that points to it to facilitate the reverse process.

    For the example list 1 -> 2 -> 3 -> 4 -> 5 in the problem statement, it will become 0 -> 1 -> 2 -> 3 -> 4 -> 5 (we init new_head -> val to be 0). Then we set a pointer pre to new_head and another cur to head. Then we insert cur -> next after pre for k - 1 times if the current node cur has at least k nodes after it (including itself). After reversing one k-group, we update pre to be cur and cur to be pre -> next to reverse the next k-group.

    The code is as follows.

    class Solution { 
    public: 
        ListNode* reverseKGroup(ListNode* head, int k) {
            if (!hasKNodes(head, k)) return head;
            ListNode* new_head = new ListNode(0);
            new_head -> next = head;
            ListNode* pre = new_head;
            ListNode* cur = head;
            while (hasKNodes(cur, k)) {
                for (int i = 0; i < k - 1; i++) {
                    ListNode* temp = pre -> next;
                    pre -> next = cur -> next;
                    cur -> next = cur -> next -> next;
                    pre -> next -> next = temp; 
                }
                pre = cur;
                cur = pre -> next;
            }
            return new_head -> next;
        }
    private:
        bool hasKNodes(ListNode* node, int k) {
            int cnt = 0;
            while (node) {
                cnt++;
                if (cnt >= k) return true;
                node = node -> next;
            }
            return false; 
        }
    };

  • 0
    J

    cool code!
    Thanks for sharing~


  • 2
    J

    btw, you didn't delete the new_head.
    Maybe a local variable is enough.


  • 0

    Hi, justyu. Thank you for your remind. Yeah, new_head needs to be deleted. Well, since it does not affect the result, I omit this step to make the code look clean :-)


  • 0
    S

    I dont thing you need to cound size every single time. you know that after reverse it will get shorter for k items. And again I see the tension - "the shorter - the better". No. the shorter - the harder to understand and harder to support.


  • 1
    Y

    I strongly suggest that you use local dummy node instead of using heap allocated node.

    Two reasons:
    (1)Once you use keyword new , then you have to delete the instance. Otherwise, it's memory leak. Ignoring that is a red flag during interview. I understand that you know about this and want to keep the node looks clean here. However, looks correct is more important than looks clean. The code may misguide other people, the the habit you formed here may affect yourself as well.
    (2)Dummy node give you a very clear expectation about the lifetime of an object. And also stack allocation is generally faster than heap allocation in c++.


Log in to reply
 

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