solution.md

# K 个一组翻转链表
以下错误的选项是？
## 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;
    }
};
```