LeetCode 25. K 个一组翻转链表

题目描述

分析

与两两交换是对应的题目。依然是从dummy结点开始，首先要判断之后是否还有K个结点。如果不足，结束翻转。这里要分为三个部分进行处理，包含：K个结点的翻转、左边指向改变、右边被指向改变。
K个结点的翻转：相当于是改K-1根线，因此循环K-1次。每次只修改一根线。最终改完a会踩在翻转前第K个结点的位置，b就是下一组了。
左边指向改变：原来是指向下一个结点的指针，要改为指向下一个K部分（此时该结点为本部分的尾端）。
右边被指向改变：原来是被上一个结点指向，要改为被上一个K部分指向（此时该结点为本部分的头部）。

代码（Java）——O(n)+O(1)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while (true) {
            ListNode temp = cur;
            // 判断是否足K的长度
            for (int i = 0; i < k && temp != null; i ++) temp = temp.next;
            if (temp == null) break;

            ListNode first = cur.next, second = first.next;
            // 改变了K个结点之间K-1条链的方向
            for (int i = 0; i < k - 1; i ++) {
                ListNode secondNext = second.next;
                second.next = first;
                first = second;
                second = secondNext;
            }
            ListNode tempFirst = cur.next; 
            cur.next = first;
            tempFirst.next = second;
            cur = tempFirst;
        }
        return dummy.next;
    }
}

递归代码——O(n)+O(n)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 检查是否还有K个结点
        ListNode cur = head;
        int count = 0;
        // 成功走K次后，到达下一组的头结点
        // 这里的cur很重要，同时对下一组的头结点进行了判断
        while (cur != null && count < k) {
            cur = cur.next;
            count ++;
        }

        if (count < k) return head;

        // 遍历完后firts就是翻转后的头结点
        ListNode first = head, second = first.next;
        for (int i = 0; i < k - 1; i ++) {
            ListNode secondNext = second.next;
            second.next = first;
            first = second;
            second = secondNext;
        }

        head.next = reverseKGroup(cur, k);
        return first;
    }
}