单链表分组反转

题目描述

这其实是⼀道变形的链表反转题，⼤致描述如下 给定⼀个单链表的头节点 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不调整，因为不够⼀ 组

参考文档

https://juejin.cn/post/6844903910386171912

解题思路

1、先写出一个方法，能够支持局部链表的逆序

func turnNode(node *Node, start, len int) {
    //先找到需要操作的位置
    a := node
    for i := 0; i < start-1; i++ {
        a = a.Next
    }
    b := a.Next
    c := b.Next
    //寻找len后面的节点
    d := a
    for i := 0; i < len; i++ {
        d = d.Next
    }
    b.Next = d.Next
    a.Next = d
    for i := 0; i < len-1; i++ {
        a = b
        b = c
        c = c.Next
        b.Next = a
    }
}

2.然后开始计算这个链表，从第几个位置开始逆序即可

func Test1(t *testing.T) {
    node := &Node{
        Value: 1,
        Next: &Node{
            Value: 2,
            Next: &Node{
                Value: 3,
                Next: &Node{
                    Value: 4,
                    Next: &Node{
                        Value: 5,
                        Next: &Node{
                            Value: 6,
                            Next: &Node{
                                Value: 7,
                                Next: &Node{
                                    Value: 8,
                                },
                            },
                        },
                    },
                },
            },
        },
    }
    // 计算需要翻转的位置
    var len int
    node2 := node
    for node2 != nil {
        len++
        node2 = node2.Next
    }
    k := 3
    y := len % k
    for i := 0; i < len/k; i++ {
        turnNode(node, i*k+y, k)
    }
    for node != nil {
        fmt.Println(node.Value)
        node = node.Next
    }
}