题解 | #链表中的节点每k个一组翻转#

提供一种用栈实现的方法，用栈实现比单一循环虽然效率低但好在逻辑上更连贯，改成递归也更容易。

整体思路为：

1. 从头开始遍历整个链表，将链表每k个节点存入栈中（只需入栈每组的头节点），不够k个则遍历结束
2. 对每组进行出栈进行翻转；由于栈有后进先出的特性，所以是从倒数第一组开始往前翻转的
3. 如果变量定义得当，从后往前翻转即可实现每组翻转后的自动连接，k=2时的翻转过程如图：

分组过程：

翻转过程：

/**栈实现*/
class Solution
{
public:
  ListNode *reverseKGroup(ListNode *head, int k)
  {
    std::stack<ListNode *> nodes;
    ListNode *dummy_head = new ListNode(-1);
    dummy_head->next = head;
    ListNode *tail = dummy_head;
    ListNode *sub_head = tail->next;
    // 将链表按k个分组存入栈中
    while (tail != nullptr)
    {
      // 循环结束后，tail指向待翻转子链表的最后一个节点
      sub_head = tail->next;
      for (int i = 1; i <= k && tail != nullptr; i++)
      {
        tail = tail->next;
      }

      if (tail)
      {
        nodes.push(sub_head);
      }
      else
      {
        // 说明不够k个，且此时tail=nullptr;
        // sub_head指向剩余节点
        // 这种情况下什么都不用做
      }
    }

    // 对nodes里各子链表进行翻转
    ListNode *prev = sub_head;
    ListNode *curr = nullptr;
    while (!nodes.empty())
    {
      curr = nodes.top();
      nodes.pop();
      for (int i = 1; i <= k; ++i)
      {
        ListNode *next = curr->next;
        curr->next = prev; // 第一次循环时，连接到已经翻转过的链表头节点
        prev = curr;
        curr = next;
      }
      // 每次循环结束后，prev指向当前翻转后子链表的头节点
    }
    return prev;
  }
};