题解 | #链表中的节点每k个一组翻转#

package main
import . "nc_tools"

/*
//递归，时空On
func reverseKGroup( head *ListNode ,  k int ) *ListNode {
    // write code here
    cur := head

    for i := 0; i < k; i++ {
        if cur == nil {
            return head
        }
        cur = cur.Next
    }

    pre := reverseKGroup(cur, k)
    curr := head

    for i := 0; i < k; i++ {
        temp := curr.Next
        curr.Next = pre
        pre = curr
        curr = temp
    }
    return pre
}
*/


//迭代，时间On，空间O1
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next : head}
    prem := dummy

    for head != nil {                               //分组
        cur := prem                //不是head哦
        for i := 0; i < k; i++ {
            cur = cur.Next
            if cur == nil {
                return dummy.Next
            }
        }

        tmp := cur.Next
        head, cur = myReverse(head, cur)            //翻转

        prem.Next = head                            //合并
        cur.Next = tmp

        prem = cur
        head = cur.Next
    }
    return dummy.Next
}


func myReverse(head, cur *ListNode) (*ListNode, *ListNode) {
    pre := cur.Next
    modn := head

    for pre != cur {
        temp := modn.Next
        modn.Next = pre
        pre = modn
        modn = temp
    }
    return cur, head
}