golang 实现链表反转的升级版

js
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// ================= 核心函数 =================

// 从尾部开始，每K个一组翻转
func reverseKFromTail(head *ListNode, k int) *ListNode {
	if head == nil || k <= 1 {
		return head
	}

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

	// 2. 前面不参与翻转的节点数
	remain := n % k
	if remain == n {
		return head
	}

	// 3. 找到翻转起点
	dummy := &ListNode{Next: head}
	pre := dummy

	for i := 0; i < remain; i++ {
		pre = pre.Next
	}

	// 4. 从这里开始做K组翻转
	pre.Next = reverseK(pre.Next, k)

	return dummy.Next
}

// 标准K组翻转（从头开始的经典写法）
func reverseK(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Next: head}
	pre := dummy

	for {
		tail := pre

		// 判断是否有K个节点
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil {
				return dummy.Next
			}
		}

		next := tail.Next

		// 翻转这一组
		start := pre.Next
		newHead, newTail := reverse(start, tail)

		// 接回去
		pre.Next = newHead
		newTail.Next = next

		pre = newTail
	}
}

// 翻转 [head, tail] 区间
func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
	prev := tail.Next
	cur := head

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

	return tail, head
}

// ================= 辅助函数 =================

// 构建链表
func buildList(nums []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy

	for _, v := range nums {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}

	return dummy.Next
}

// 打印链表
func printList(head *ListNode) {
	cur := head
	for cur != nil {
		fmt.Printf("%d -> ", cur.Val)
		cur = cur.Next
	}
	fmt.Println("null")
}

// ================= 测试 =================

func main() {
	// 示例：
	// 1→2→3→4→5→6→7→8
	head := buildList([]int{1, 2, 3, 4, 5, 6, 7, 8})

	k := 3

	fmt.Println("原链表：")
	printList(head)

	newHead := reverseKFromTail(head, k)

	fmt.Println("处理后：")
	printList(newHead)
}