题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

题目分析

指针指向头部，判断剩余长度是否达到 k。
如果长度足够，则只对前 k 个位置做反转，反转后把剩余部分的连接做好。后续局部的头和尾会发生互换，将指针指向新的局部尾。
不断重复，直到剩余部分不足k个。

Java

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode fake = new ListNode(0, head);
    ListNode cur = fake;
    while (length(cur.next) >= k) {
        ListNode pHead = reverseFirstK(cur.next, k);
        ListNode pTail = cur.next;
        cur.next = pHead;
        cur = pTail;
    }

    return fake.next;
}

private int length(ListNode head) {
    int length = 0;
    while (head != null) {
        head = head.next;
        length++;
    }
    return length;
}

private ListNode reverseFirstK(ListNode head, int k) {
    ListNode pre = null, cur = head;
    while (cur != null && k > 0) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
        k--;
    }
    head.next = cur;
    return pre;
}

Kotlin

fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    val fake = ListNode(0)
    fake.next = head
    var cur: ListNode? = fake
    while (length(cur?.next) >= k) {
        val pTail = cur?.next
        val pHead = reverseFirstK(cur?.next, k)
        cur?.next = pHead
        cur = pTail
    }

    return fake.next
}

private fun length(head: ListNode?): Int {
    var length = 0
    var cur = head
    while (cur != null) {
        cur = cur.next
        length++
    }
    return length
}

private fun reverseFirstK(head: ListNode?, k: Int): ListNode? {
    var tail: ListNode? = null
    var cur: ListNode? = head
    var count = k
    while (cur != null && count > 0) {
        val temp = cur.next
        cur.next = tail
        tail = cur
        cur = temp
        count--
    }
    head?.next = cur
    return tail
}