25. K 个一组翻转链表

class Solution {
  ListNode *Reverse(ListNode *Head, int Length) {
    ListNode *RevHead = nullptr;
    ListNode *FwdHead = Head;
    while (Length--) {
      ListNode *FwdNext = FwdHead->next;
      FwdHead->next = RevHead;
      RevHead = FwdHead;
      FwdHead = FwdNext;
    }
    return RevHead;
  }

public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *Tracking = head;
    // Tracking is at tail after this iteration process.
    for (int i = 0; i < k; ++i) {
      if (!Tracking)
        return head;
      Tracking = Tracking->next;
    }

    ListNode Dummy(0, head);
    Dummy.next = Reverse(Dummy.next, k);
    // At this time, head has been moved to tail.
    head->next = reverseKGroup(Tracking, k);
    return Dummy.next;
  }
};

class Solution {
  ListNode *Reverse(ListNode *head) {
    ListNode *Prev = nullptr;
    while (head) {
      ListNode *Next = head->next;
      head->next = Prev;
      Prev = head;
      head = Next;
    }
    return Prev;
  }

public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *NewHead = head;
    ListNode *Prev = nullptr;
    while (true) {
      ListNode *Next = head;
      ListNode DNextPrev(0, Next), *NextPrev = &DNextPrev;
      // Advance Next for next round of reverse operation.
      for (int i = 0; i < k; ++i) {
        if (!Next) {
          // Not divisible, just connect and return.
          if (Prev)
            Prev->next = head;
          return NewHead;
        }
        NextPrev = NextPrev->next;
        Next = Next->next;
      }
      // Break the link in order to Reverse().
      NextPrev->next = nullptr;
      ListNode *RevHead = Reverse(head);
      // Nullity check for Prev, and then assign head to it in order to connect
      // two consecutive groups in the next iteration.
      if (Prev)
        Prev->next = RevHead;
      Prev = head;
      // NewHead only need to be assigned for once.
      if (NewHead == head)
        NewHead = RevHead;
      head = Next;
    }
  }
};

class Solution {
  std::pair<ListNode *, ListNode *> Reverse(ListNode *First, ListNode *Last) {
    // In fact we can also just default construct. Either way the list needs to
    // be manually put back into original, because we need the NEWEST head
    // instead of this old, not reversed head.
    ListNode *Prev = Last->next;
    ListNode *Curr = First;
    while (Prev != Last) {
      ListNode *Next = Curr->next;
      Curr->next = Prev;
      Prev = Curr;
      Curr = Next;
    }
    return {Last, First};
  }

public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    // The likely most important function of Dummy is to return a (possibly
    // changed) head easily. It's not just for iteration. See the two return
    // statements below.
    ListNode Dummy(0, head), *Prev = &Dummy;
    while (head) {
      ListNode *Last = Prev;
      // Advance Last.
      for (int i = 0; i < k; ++i) {
        Last = Last->next;
        if (!Last)
          return Dummy.next;
      }
      // Keep in mind that if we have a Prev pointer, there's no need anymore
      // to create another Curr pointer. Just Prev->next is enough.
      ListNode *Next = Last->next;
      std::tie(head, Last) = Reverse(head, Last);
      // Connect the reversed list back to the original list.
      Prev->next = head;
      // Advance Prev and head for next iteration.
      Prev = Last;
      head = Next;
    }
    return Dummy.next;
  }
};

class Solution {
  ListNode *Reverse(ListNode *Head) {
    ListNode *Prev = nullptr;
    while (Head) {
      ListNode *Next = Head->next;
      Head->next = Prev;
      Prev = Head;
      Head = Next;
    }
    return Prev;
  }

public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *Curr = head;
    ListNode Pre(0, head), *Prev = &Pre;
    while (Curr) {
      ListNode NextPre(0, Curr), *NextPrev = &NextPre;
      for (int i = 0; i < k; ++i) {
        NextPrev = NextPrev->next;
        if (!NextPrev) {
          Prev->next = Curr;
          goto Finish;
        }
      }
      ListNode *Next = NextPrev->next;
      NextPrev->next = nullptr;

      ListNode *RevCurr = Reverse(Curr);
      // The difference between Pre and Prev are really subtle here! As you can
      // see, the FIRST assignment of Prev->next does change the value of
      // Pre.next, since at this time, Prev == &Pre.
      Prev->next = RevCurr;
      // However, when we advance Prev to Curr, even for once, Prev == &Pre NO
      // LONGER holds. That's why we don't need complicated temporary variables
      // to make sure that Pre.next points to our new head.
      Prev = Curr;
      Curr = Next;
    }
Finish:
    return Pre.next;
  }
};