变形的链表反转

题目描述：

给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）

示例：

链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。

思路：

根据链表长度 length 和给定的整数 k，计算需要反转的组数 groups，以及不进行反转的头部剩余节点数量 remaining。

创建一个哑节点 dummy，使其指向链表的头节点。接下来，创建一个指针 preGroupEnd，初始化为指向哑节点。将 preGroupEnd 指针向后移动 remaining 个节点，使其指向最后一个不进行反转的头部剩余节点。这样，preGroupEnd 初始时指向不需要反转的部分的末尾。

实现：

package main

import (
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroupFromEnd(head *ListNode, k int) *ListNode {
	if head == nil || k <= 1 {
		return head
	}

	// 计算链表长度
	length := 0
	cur := head
	for cur != nil {
		length++
		cur = cur.Next
	}

	// 计算需要反转的组数
	groups := length / k

	if groups == 0 {
		return head
	}

	// 计算剩余节点数量
	remaining := length % k

	dummy := &ListNode{Next: head}
	preGroupEnd := dummy
	for i := 0; i < remaining; i++ {
		preGroupEnd = preGroupEnd.Next
	}

	for i := 0; i < groups; i++ {
		start := preGroupEnd.Next
		end := preGroupEnd
		for j := 0; j < k; j++ {
			end = end.Next
		}
		nextGroupStart := end.Next
		end.Next = nil

		// 逆序当前组
		newStart, newEnd := reverseList(start)
		preGroupEnd.Next = newStart
		newEnd.Next = nextGroupStart
		preGroupEnd = newEnd
	}

	return dummy.Next
}

func reverseList(head *ListNode) (*ListNode, *ListNode) {
	var prev *ListNode
	cur := head

	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}

	return prev, head
}

func main() {
	head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, &ListNode{6, &ListNode{7, &ListNode{8, nil}}}}}}}}
	k := 3

	newHead := reverseKGroupFromEnd(head, k)
	for newHead != nil {
		if newHead.Next == nil {
			fmt.Printf("%d -> null", newHead.Val)
		} else {
			fmt.Printf("%d -> ", newHead.Val)
		}
		newHead = newHead.Next
	}
}