LeetCode.25.K 个一组翻转链表（困难）

题目

LeetCode.25.K 个一组翻转链表（困难）

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

题解

每组翻转后最关键的在于每一组的头尾节点变化了，要把每组重新正确的连接上，梳理整个翻转过程就比较清楚了。

从左到右找到第k个节点，相当于知道了一组节点的头节点和尾节点，对这一组节点进行翻转，记录翻转后的尾节点，在下一组翻转过后，把上一组记录的新尾节点指向下一组的新头节点即可。

边界处理

如果发现最后一组不足k个，不做翻转。

递归

class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        if (head == null) return null
        var tail: ListNode? = head
        for (i in 1..k) {
            if (tail == null) return head
            tail = tail.next
        }
        val newHead = reverse(head, tail)
        head.next = reverseKGroup(tail, k)
        return newHead
    }
    
    // 翻转链表，返回新链表头节点
    private fun reverse(head: ListNode?, tail: ListNode?): ListNode? {
        var pre: ListNode? = null
        var cur: ListNode? = head
        while (cur != tail) {
            val next = cur?.next
            cur?.next = pre
            pre = cur
            cur = next
        }
        return pre
    }
}

时间复杂度O(n)：n为链表节点总数。
空间复杂度O(n/k)：递归一次占用一个方法栈，空间占用多少就看递归深度多少，n个节点每次划分k个一组，一共要递归n/k次。

迭代

class Solution {
    /**
     * 如果一边遍历一边翻转，最后一段长度不足k时也反转了就不对了，所以得先有一个指针往后探路，探到有路了再进行反转
     */
    fun reverseKGroup(head: ListNode, k: Int): ListNode {
        // 1. 创建一个虚节点，这样可以统一操作链表的代码，不用做边界情况处理
        val dummyHead = ListNode(0)
        dummyHead.next = head
        // 2. 开拓者指针，往后走k次，如果走了k次后，开拓者不为null，说明是有k个节点，可以翻转；初始时还没走，所以应该在头节点的前一个位置
        var pioneer: ListNode? = dummyHead

        // 7. 记录当前待翻转区域前面的一个节点，用于把之前已反转的部分跟当前区域反转后重新连接起来，初始时是头节点的前一个节点
        var predecessor: ListNode? = dummyHead

        // 3. while循环一开始可能不知道是什么条件，可以先写while(true)，先写遍历代码
        // 13. pioneer探路前，指向的是要翻转的区域的前驱结点，如果不存在要翻转的区域，就不用遍历了，如果还有要翻转的区域则需要继续探路；如果后面不足k个节点，会在循环内break
        while (pioneer?.next != null) {
            // 4. 开拓者要探k次路，如果后面不足k个结点，pioneer应当为null
            for (i in 0 until k) {
                pioneer = pioneer?.next
                if (pioneer == null) break
            }

            // 5. 一开始还没开始翻转，就发现链表不足k个节点的话，按照题意不用翻转，所以就什么都不用做了，先break
            if (pioneer == null) break

            // 6. pioneer不为null，说明是有k个节点的，可以翻转
            // 翻转主要是要解决翻转区域前后节点的连接问题，翻转后翻转区域的头尾都变了
            // 需要把翻转区域前后节点先保存下来，翻转后再重新连接翻转区域到主链表上
            // 当前待翻转区域尾节点就是pioneer，翻转区域后面的节点就是pioneer.next
            val successor = pioneer?.next
            // 翻转区域前面的节点还没有记录过，需要有个变量记录一下，到上面定义一下

            // 8. 翻转链表链表需要知道头结点，需要记录待翻转区域头节点，翻转后这个节点就变成了尾节点
            val newTail = predecessor?.next

            // 9. 把当前正要翻转区域跟主链表断开连接再做翻转，这样会比较方便，因为本来就是要重新连接的，最后再重新连接上
            predecessor?.next = null
            pioneer?.next = null

            // 10. 翻转链表
            val newHead = reverse(newTail)

            // 11. 重新把翻转后的链表连接到原链表
            predecessor?.next = newHead
            newTail?.next = successor

            // 12. 重置前驱指针和开拓者指针，都指向当前翻转区域的尾节点
            predecessor = newTail
            pioneer = newTail
        }

        // 返回新的头节点
        val newHead = dummyHead.next
        dummyHead.next = null
        return newHead
    }

    /**
     * 翻转链表，返回翻转后的头节点
     */
    private fun reverse(head: ListNode?): ListNode? {
        var pre: ListNode? = null
        var cur: ListNode? = head
        while (cur != null) {
            val next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        }
        return pre
    }
}

时间复杂度O(n)：n为链表节点总数，需要遍历所有节点。
空间复杂度O(1)：只用了常数个变量。