package top100liked

import (
	"fmt"
	"testing"
)

// https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked

type ListNode struct {
	Val  int
	Next *ListNode
}

// 提交记录 3
// 你就说快不快吧
// func reverseKGroup(head *ListNode, k int) *ListNode {
// 	if k == 1 {
// 		return head
// 	}
// 	nodes := []*ListNode{}
// 	p := head
// 	nodes = append(nodes, &ListNode{0, head})
// 	for p != nil {
// 		nodes = append(nodes, p)
// 		p = p.Next
// 	}
// 	tmp := nodes[0]
// 	for i := range (len(nodes) - 1) / k {
// 		tmp.Next = nodes[(i+1)*k]
// 		nodes[i*k+1].Next = nodes[(i+1)*k].Next
// 		for j := range k - 1 {
// 			nodes[(i+1)*k-j].Next = nodes[(i+1)*k-j-1]
// 		}
// 		tmp = nodes[i*k+1]
// 	}
// 	return nodes[0].Next
// }

func reverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Next: head}
	prev := dummy
	for {
		// 检查剩余节点是否够 k 个
		tail := prev
		for range k {
			tail = tail.Next
			if tail == nil {
				return dummy.Next
			}
		}
		next := tail.Next // 下一组的起点
		// 翻转 [prev, tail] 这 k 个节点
		p := prev.Next
		var reversedHead, reversedTail *ListNode
		reversedTail = p // 翻转后 p 变成尾部
		var pre *ListNode
		for range k {
			tmp := p.Next
			p.Next = pre
			pre = p
			p = tmp
		}
		reversedHead = pre
		// 接回原链表
		prev.Next = reversedHead
		reversedTail.Next = next
		prev = reversedTail
	}
}

func Test1(t *testing.T) {
	input := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 4,
					Next: &ListNode{
						Val:  5,
						Next: nil,
					},
				},
			},
		},
	}
	output := reverseKGroup(input, 2)
	for output != nil {
		fmt.Print(output.Val, " ")
		output = output.Next
	}
}

func Test2(t *testing.T) {
	input := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 4,
					Next: &ListNode{
						Val:  5,
						Next: nil,
					},
				},
			},
		},
	}
	output := reverseKGroup(input, 3)
	for output != nil {
		fmt.Print(output.Val, " ")
		output = output.Next
	}
	fmt.Println()
}

func Test3(t *testing.T) {
	input := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val:  2,
			Next: nil,
		},
	}
	output := reverseKGroup(input, 2)
	for output != nil {
		fmt.Print(output.Val, " ")
		output = output.Next
	}
	fmt.Println()
}