LeetCode-Reverse Nodes in K-Group

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

因为题目要求空间复杂度为常数，并且不能改变链表节点中元素的值，所以只能从移动链表上去想。

最开始的想法是按照最直接的思路，先判断是否可以逆转，如果可以的话就使用一个双层循环去逆转（每一轮将前面的一个元素移动到最后），这样的复杂度是 O(n^3)，居然 Accept 了。但是的确效率太低了。

ps：在移动链表的时候一定要想清楚上一步对其产生的影响，不然肯定全都是 bug 呀。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head==nil {
        return nil
    }
    ret:=new(ListNode)
    ret.Next=head
    start,nextRound:=ret,ret
    Loop:
    for {
        for i:=0;i<k;i++ {
            if nextRound.Next==nil {
                break Loop
            }
            nextRound=nextRound.Next
        }
        nextRound=start.Next
        for i:=k-1;i>0;i-- {
            now:=start
            for j:=0;j<i;j++ {
                t:=now.Next
                now.Next=t.Next
                t.Next=now.Next.Next
                now.Next.Next=t
                now=now.Next
            }
        }
        start=nextRound
    }

    return ret.Next
}

看了一下 Discussion 中的思路，使用了递归和分段逆转，递归利用了我的解法中判断是否符合循环，使其不至于被浪费。而逆转算法比我高效很多，我的方法是挨个遍历，他的算法是直接将每一步的箭头倒转过来。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    n:=head
    i:=0
    for n!=nil && i<k {
        n=n.Next
        i++
    }
    if i==k {
        n=reverseKGroup(n,k)
        for ;i>0;i-- {
            t:=head.Next
            head.Next=n
            n=head
            head=t
        }
        head=n
    }
    return head
}

发现效率提高了一些，但是还是远远没有达到排名前面答案的水准。

于是打开排名靠前的答案看了一下，发现它们都没有遵循题目中的限制条件，所以就暂且不管了。