solution.md

# K 个一组翻转链表

<p>给你一个链表，每 <em>k </em>个节点一组进行翻转，请你返回翻转后的链表。</p><p><em>k </em>是一个正整数，它的值小于或等于链表的长度。</p><p>如果节点总数不是 <em>k </em>的整数倍，那么请将最后剩余的节点保持原有顺序。</p><p><strong>进阶：</strong></p><ul>	<li>你可以设计一个只使用常数额外空间的算法来解决此问题吗？</li>	<li><strong>你不能只是单纯的改变节点内部的值</strong>，而是需要实际进行节点交换。</li></ul><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0025.Reverse%20Nodes%20in%20k-Group/images/reverse_ex1.jpg" style="width: 542px; height: 222px;" /><pre><strong>输入：</strong>head = [1,2,3,4,5], k = 2<strong><br />输出：</strong>[2,1,4,3,5]</pre><p><strong>示例 2：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0025.Reverse%20Nodes%20in%20k-Group/images/reverse_ex2.jpg" style="width: 542px; height: 222px;" /><pre><strong>输入：</strong>head = [1,2,3,4,5], k = 3<strong><br />输出：</strong>[3,2,1,4,5]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>head = [1,2,3,4,5], k = 1<strong><br />输出：</strong>[1,2,3,4,5]</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>head = [1], k = 1<strong><br />输出：</strong>[1]</pre><ul></ul><p><strong>提示：</strong></p><ul>	<li>列表中节点的数量在范围 <code>sz</code> 内</li>	<li><code>1 <= sz <= 5000</code></li>	<li><code>0 <= Node.val <= 1000</code></li>	<li><code>1 <= k <= sz</code></li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode() : val(0), next(nullptr){};
    ListNode(int x) : val(x), next(nullptr){};
    ListNode(int x, ListNode *next) : val(x), next(next){};
};
```

### after

```cpp

```

## 答案

```cpp
class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        if (head == NULL || head->next == NULL || k == 1)
            return head;
        ListNode *cur = head;
        int i = 1;
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        if (i < k)
            return head;
        stack<ListNode *> s;
        ListNode *p = head;
        while (s.size() != k)
        {
            s.push(p);
            p = p->next;
        }
        ListNode *phead = s.top();
        s.pop();
        ListNode *p2 = phead;
        while (!s.empty())
        {
            p2->next = s.top();
            s.pop();
            p2 = p2->next;
            p2->next = NULL;
        }
        while (p != NULL)
        {
            s.push(p);
            p = p->next;
            if (s.size() == k)
            {
                while (!s.empty())
                {
                    p2->next = s.top();
                    s.pop();
                    p2 = p2->next;
                    p2->next = NULL;
                }
            }
        }
        if (!s.empty())
        {
            stack<ListNode *> s2;
            while (!s.empty())
            {
                s2.push(s.top());
                s.pop();
            }
            while (!s2.empty())
            {
                p2->next = s2.top();
                s2.pop();
                p2 = p2->next;
            }
        }
        return phead;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<ListNode *> reverse(ListNode *head, int k)
    {
        ListNode *newhead = NULL;
        vector<ListNode *> res;
        res.push_back(head);
        int i = 0;
        ListNode *head1 = head;
        while (head1)
        {
            i++;
            head1 = head1->next;
            if (i == k)
            {
                break;
            }
        }
        if (i < k)
        {
            return res;
        }
        while (k)
        {
            ListNode *nexthead = head->next;
            head->next = newhead;
            newhead = head;
            head = nexthead;
            k--;
        }
        res.push_back(newhead);
        res.push_back(head);
        return res;
    }
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *newhead = new ListNode(0);
        ListNode *tmp = newhead;
        while (head)
        {
            vector<ListNode *> res = reverse(head, k);
            if (res.size() == 3)
            {
                tmp->next = res[1];
                tmp = res[0];
                head = res[2];
            }
            else
            {
                tmp->next = res[0];
                head = NULL;
            }
        }
        return newhead->next;
    }
};
```

### B

```cpp
class Solution
{
public:
    ListNode *reverseK(ListNode *pre, ListNode *lat)
    {
        ListNode *lpre = pre->next;
        ListNode *cur = lpre->next;
        while (cur != lat)
        {
            lpre->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = lpre->next;
        }
        return lpre;
    }
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *h = new ListNode(-1);
        h->next = head;
        ListNode *cur = head;
        int t = 1;
        ListNode *pre = h;
        while (cur != NULL)
        {
            if (t % k == 0)
            {
                pre = reverseK(pre, cur->next);
                cur = pre->next;
            }
            else
                cur = cur->next;

            t += 1;
        }
        return h->next;
    }
};
```

### C

```cpp
class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        int len = 0;
        struct ListNode dummy, *prev = &dummy;
        dummy.next = head;
        for (; head != nullptr; head = head->next)
        {
            if (++len % k == 0)
            {
                struct ListNode *p = prev->next;
                while (prev->next != head)
                {
                    struct ListNode *q = p->next;
                    p->next = q->next;
                    q->next = prev->next;
                    prev->next = q;
                }
                prev = p;
                head = p;
            }
        }
        return dummy.next;
    }
};
```