# K 个一组翻转链表
---

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

k是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。

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

:::success

package main

import "fmt"

func main() {
	arr := []int{1, 2, 3, 4, 5, 6, 7, 8}

	p := &ListNode{arr[0], nil}

	for _, r := range arr[1:] {
		p.Append(r)
	}

	fmt.Println("反转之前的结果数据")
	p.Show()

	fmt.Println("反转之后的结果数据")
	res := reverseKGroup(p, 3)
	res.Show()
}

func (h *ListNode) Append(i int) {
	for h.Next != nil {
		h = h.Next
	}
	h.Next = &ListNode{Value:i}
}

func (h *ListNode) Show() {
	for h != nil {
		if h.Next != nil {
			fmt.Printf("%d->", h.Value)
		} else {
			fmt.Printf("%d\n", h.Value)
		}
		h = h.Next
	}
}

type ListNode struct {
	Value int
	Next  *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	var (
		cur, next, p, q *ListNode
		size, index     int
	)

	p, q = head, head

	for p != nil && size < k { // 每k个节点一组，子链表
		p = p.Next
		size++
	}

	if size == k {
		for q != nil && index < k { // 反转子链表
			next = q.Next
			q.Next, cur, q = cur, q, next
			index++
		}

		if next != nil { // 还未遍历完主链表所有节点，则继续递归地执行上述过程
			head.Next = reverseKGroup(next, k) // head指向子链表反转后的尾节点
		}

		return cur // cur 子链表反转后的头结点
	}

	return head // 所有节点加完后子链表长度不足k，不反转
}

- 结果输出

反转之前的结果数据
1->2->3->4->5->6->7->8
反转之后的结果数据
3->2->1->6->5->4->7->8

:::

###### tags: `LeeCode`