# 25. K 个一组翻转链表

## Link

{% embed url="<https://leetcode.cn/problems/reverse-nodes-in-k-group/>" %}

## Problem

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

![](https://1992890748-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F0qYY1ILl1K1crNjGMFmh%2Fuploads%2Fc6nnVmsJg5MsINi2JOpR%2Fimage.png?alt=media\&token=1838257f-cd46-47e4-b33f-dffe2323a8b5)

{% code overflow="wrap" %}

```
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
```

{% endcode %}

示例2：

![](https://1992890748-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F0qYY1ILl1K1crNjGMFmh%2Fuploads%2Fq38qBUX1MMBtYJ3WE8kx%2Fimage.png?alt=media\&token=1ba703d7-8f8c-410f-ab9a-5b96593e4584)

{% code overflow="wrap" %}

```
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
```

{% endcode %}

提示：

* 链表中的节点数目为 `n`
* `1 <= k <= n <= 5000`
* `0 <= Node.val <= 1000`

## Solution

{% tabs %}
{% tab title="Go" %}

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{-1, head}
    cur, pre := dummy, dummy

    cnt := 0
    for cur.Next != nil {
        cur = cur.Next
        cnt++
        if cnt%k == 0 {
            next := cur.Next
            cur.Next = nil
            nh, nt := reverse(pre.Next)
            
            pre.Next = nh
            nt.Next = next

            pre, cur = nt, nt
        }
    } 

    return dummy.Next
}

func reverse(head *ListNode) (*ListNode, *ListNode){
    cur := head
    var pre, next *ListNode

    for cur != nil {
        next = cur.Next
        cur.Next = pre
        pre = cur 
        cur = next
    }
    return pre, head
}
```

{% endtab %}

{% tab title="C++" %}

```cpp
```

{% endtab %}
{% endtabs %}