LeetCode 25. K 个一组翻转链表

25. K 个一组翻转链表

解题思路

参考代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计链表长度
        int n = 0;
        ListNode node = head;
        while(node != null) {
            n ++;
            node = node.next;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode p0 = dummy;
        ListNode pre = null;
        ListNode cur = head;

        for(; n >= k; n -= k) {
            for(int i = 0; i < k; i ++) {
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }

            ListNode nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }
        return dummy.next;
    }
}

最后不足 $k$ 个的剩余节点也进行翻转

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode node = head;
        while(node != null) {
            node = node.next;
            n ++;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode p0 = dummy;
        ListNode pre = null;
        ListNode cur = head;

        for(; n >= k; n -= k) {
            for(int i = 0; i < k; i ++) {
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            ListNode nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }
        
        // 反转剩余的不足k个节点
        if (cur != null) {
            // 先断开连接，避免循环
            p0.next = null;
            // 反转剩余节点
            ListNode remainingPre = null;
            ListNode remainingCur = cur;
            while (remainingCur != null) {
                ListNode nxt = remainingCur.next;
                remainingCur.next = remainingPre;
                remainingPre = remainingCur;
                remainingCur = nxt;
            }
            // 连接到原链表
            p0.next = remainingPre;
        }
        
        return dummy.next;
    }
}

ACM 模式