25. K 个一组翻转链表

栈实现

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Val:  -1,}
    dummy.Next = head
    pre :=dummy
    stack := make([]*ListNode,0)
    n := k
    for pre.Next!=nil{
        tmp :=pre.Next
        for tmp!= nil&&n>0{
            stack = append(stack,tmp)
            tmp = tmp.Next
            n--
        }
        topNode := stack[len(stack)-1]
        nextNode :=topNode.Next
        if n==0{
            for len(stack)>0{
                topNode :=stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                pre.Next = topNode
                pre = pre.Next
            }
            pre.Next = nextNode
            n = k
        }else {
            return dummy.Next
        }
    }
    return dummy.Next
}

或者链表反转

func revert(head *ListNode)*ListNode{
    var pre *ListNode
    curr := head
    for curr!= nil{
        pre,curr,curr.Next = curr,curr.Next,pre
    }
    return pre
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Val:  -1,}
    dummy.Next = head
    pre,curr,end := dummy,dummy,dummy
    for end!=nil{
        // 获取当前节点
        curr = pre.Next
        // 获取结束结点
        for i:=0;i<k;i++{
            end = end.Next
            if end == nil{
                return dummy.Next
            }
        }
        // 暂存后节点
        next := end.Next
        end.Next = nil// 至空
        pre.Next = revert(curr)
        // 反转结束后当前子链表的头结点
        pre,end = curr,curr// 都是当前值
        curr.Next = next//需要把链表串起来
    }
    return dummy.Next
}