LC25 - K个一组翻转链表

package LinkedList

// reverseSubLinkedList: 反转以preStart.Next为开始位置、end为结束位置的子链
// 包括内部链表的反转，以及外部链表的连接
func reverseSubLinkedList(preStart, end *ListNode) {
    endNext := end.Next
    if preStart.Next == end {
        return
    }
    cur := preStart.Next
    var prev, next *ListNode
    for cur != endNext {
        next = cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    preStart.Next.Next = endNext
    preStart.Next = end
}

// 时间复杂度: O(n), 空间复杂度: O(1)
func reverseKGroup(head *ListNode, k int) *ListNode {
    virtualHead := new(ListNode)
    virtualHead.Next = head
    preStart, end := virtualHead, virtualHead
    for i := 0; i < k; i++ {
        end = end.Next
    }
    for {
        reverseSubLinkedList(preStart, end)
        for i := 0; i < k; i++ {
            preStart = preStart.Next
        }
        end = preStart
        for i := 0; i < k; i++ {
            end = end.Next
            if end == nil {
                return virtualHead.Next
            }
        }
    }
}

本题非常适合锻炼链表相关的编码能力。