25. Reverse Nodes in k Group - cocoder39/coco39_LC GitHub Wiki

25. Reverse Nodes in k-Group

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        pre = dummy
        while True:
            count = 0
            cur = pre
            while cur.next and count < k:
                cur = cur.next
                count += 1
            if count == k:
                pre = self.reverse(pre, cur)
            else: # count < k but head is None
                break
        return dummy.next
    
    # reverse the list from pre.next to tail
    # return new tail as pre for next segment 
    def reverse(self, pre, tail):
        new_pre = pre.next
        while pre.next != tail:
            # move node from pre.next to tail.next
            cur = pre.next 
            pre.next = cur.next
            cur.next = tail.next
            tail.next = cur
        return new_pre

find out the pre where pre->next is the head of the k nodes to be reversed. find out tail which is the last node among the k nodes to be reversed. reverse k nodes once.

pre->next is the tail node of reversed k nodes, it is also the pre of next group of k nodes. tail is the head of reversed k nodes

two bugs:

• 1 while (tmp > 0 && tail) is incorrect, which cannot guarantee tail != nullptr
• 2 tmp would be -1 instead of the expected 0 if coding like below

while (tmp-- 0 && tail->next) {
                tail = tail->next;
            }

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        
        ListNode* pre = &dummy;
        while (1) {
            int tmp = k;
            ListNode* tail = pre;
            //check tail->next instead of tail
            //because tail must be an valid node
            while (tmp > 0 && tail->next) {
                tail = tail->next;
                tmp--;
            }
            if (tmp == 0) {
                pre = reverseK(pre, tail);
            }
            else {
                break;
            }
        }
        return dummy.next;
    }
private:
    //reverse a linked list starting from pre->next and end with newhead 
    //return newtail, which is pre of next k nodes
    ListNode* reverseK(ListNode* pre, ListNode* newhead) {
        ListNode* newtail = pre->next;
        while (pre->next != newhead) {
            ListNode* cur = pre->next;
            pre->next = cur->next;
            cur->next = newhead->next; //have to know newhead, beating using int k as argument
            newhead->next = cur;
        }
        return newtail;
    }
};