[数据结构与算法]LeetCode 25 k个一组反转链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    hair := &ListNode{Next:head}
    prev:= hair
    for head !=nil {
        tail := prev
        // 找到k和节点，不够直接返回
        for i:=0;i<k;i++ {
            tail = tail.Next
            if tail == nil{
                return hair.Next
            }
        }
        // 记录下一个节点
        nex := tail.Next
        // 单纯完成反转链表
        head, tail = myReverse(head, tail)
        //返回的head和tail是目标节点，直接完成组装即可
        tail.Next = nex
        prev.Next = head
        // 完成下一次的迭代准备
        prev = tail
        head = tail.Next
    }
    return hair.Next
}

func myReverse(head, tail *ListNode)(*ListNode,*ListNode){
    // 这个完全可以创建一个空的节点
    prev := &ListNode{Next:nil}
    p := head
    // 反转链表的常规操作
    for prev!=tail{
        nex := p.Next
        p.Next = prev
        prev = p
        p = nex
    }
    return tail, head
}