25. Reverse Nodes in K Group #

题目 #

给定链表头结点 head，每 k 个结点一组进行翻转，返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果结点总数不是 k 的整数倍，将最后的结点保持原有顺序。

不能只是单纯的改变结点内部的值，而是需要进行实际的结点交换。

思路 #

代码 #

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public void reverseList(ListNode beforeHead, ListNode tail) {
        if (beforeHead == tail) return;
        ListNode afterTail = tail.next;
        ListNode prev = afterTail, cur = beforeHead.next, temp = cur.next;
        while (cur != afterTail) {
            cur.next = prev;
            prev = cur;
            cur = temp;
            if (temp != afterTail) temp = temp.next;
        }
        beforeHead.next = prev;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode sentinel = new ListNode(-1, head);
        ListNode beforeHead = sentinel, tail = sentinel;
        
        while (tail != null) {
            for (int i = 0; i < k && tail != null; i++) tail = tail.next;
            if (tail == null) return sentinel.next;
            /** ptr 指向翻转后的链表尾结点 */
            ListNode ptr = beforeHead.next;
            reverseList(beforeHead, tail);
            beforeHead = tail = ptr;
        }
        
        return sentinel.next;
    }
}