[LeetCode 25] Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.

For example,

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Diffculty
Hard

Similar Problems
[LeetCode ] Swap Nodes in Pairs Easy

Analysis

思路:

ListNode reverseKGroup(ListNode head, int k) { if(head == nullptr || head->next == nullptr || k == 1) return head; ListNode pre = head, ptr = head->next; for(int i = 1; i < k && ptr != nullptr; i++) { // reverse from node 1, which is ptr->next ListNode *next = ptr->next; ptr->next = pre; pre = ptr; ptr = next; } head->next = reverseKGroup(ptr, k); // same as swapPair() return pre; }

Swap Nodes in Pairs那题的升级版，算linked list指针操作题中难度最高最容易写错的之一。 思路很简单，就是每次反转k个节点，如果还没反转到i<k个节点就遇到尾部了，则将这i个节点再反转回来。 但要短时间内写正确却难度不小。这类题目一定要画图来验证解法是否正确。

// iterative class Solution { public: ListNode reverseKGroup(ListNode head, int k) { if(k<2) return="" head;="" listnode="" *dummy="new" listnode(0);="" dummy-="">next = head; ListNode p = dummy; while(p->next && p->next->next) { ListNode prev = p->next, cur = prev->next; int i=0; while(cur && i<k-1) { ListNode temp = cur->next; cur->next = prev; prev = cur; cur = temp; i++; }

        if(i==k-1) {    // k nodes reversed
            ListNode *temp = p->next;
            p->next->next = cur;
            p->next = prev;
            p = temp;
        }
        else {  // less than k nodes reversed before reach end
            cur = prev->next;
            prev->next = NULL;
            while(cur != p->next) {
                ListNode *temp = cur->next;
                cur->next = prev;
                prev = cur;
                cur = temp;
            }
            break;
        }
    }
    return dummy->next;
}

};

总结： 几乎用到linked list题所有的技巧。

1. p指针总是指向每次要反转的k个节点的前一个节点。因为反转后仍然要接回这个节点之后。
2. ln8：如果p指针后没有节点或只剩一个节点了，那么整个反转结束。
3. ln11-17：尝试反转k个节点，如果遇到尾部，则提前结束。i记录了反转多少次。 注意，要反转k个节点的话，实际反转指针只需要k-1次。
4. ln19-24：如果成功反转k个节点，则i=k-1。此时将反转的k个节点两头接回， 并将p移动到反转后k个节点的最后一个节点处，以备继续反转之后的k个节点。
5. ln25-35：如果没能反转k个节点就遇到尾部。则逆向还原。

ListNode reverse_k_nodes(ListNode head, int k){ if(k <= 1 || head == nullptr){ return head; } //To check if there are at least k nodes in the current linked list int count = 1; ListNode* new_head = head; while(new_head->next != nullptr && count < k){ ++count; new_head = new_head->next; }

if(count < k){
    return head;
}else{
    //Get node next to the current tail
    ListNode* previous = new_head->next;
    ListNode* current = head;
    ListNode* next = current->next;
    while(current != new_head){
        current->next = previous;
        previous = current;
        current = next;
        next = next->next;
    }
    current->next = previous;
    return new_head;
}

}

/*

• func: reverse_k_group
• goal: reverse the nodes of a linked list k at a time
• @param head: head node of the linked list
• @param k: the group number k
• return: the modified linked list / /

• keep reverse k nodes from the head until the reversing fails / ListNode reverse_k_group(ListNode head, int k){ ListNode old_head = head; ListNode new_head = reverse_k_nodes(old_head, k); ListNode ret = new_head; while(new_head != old_head){

   //Get the previous tail node ahead of next k-group
   ListNode *previous_tail = old_head;
   //Get the old head for the next iteration
   old_head = old_head->next;
   //Get the new head for this iteration
   new_head = reverse_k_nodes(old_head, k);
   //Linked the previous tail node and current new head
   previous_tail->next = new_head;
  

  }

  return ret; }