PROBLEM

25. K 个一组翻转链表

难度 困难

MY ANSWER

困难在于需要考虑的细节比较多，如何让代码更简洁。时间复杂度为O(n)，空间复杂度O(1)。

BETTER SOLUTION

通过构造一个头节点dummy指向head，就可以避免一个特殊情况判断，将上一段的尾部指向下一段的头部。使用头插法来进行局部链表的反转，例如反转序列中的 123：

prev=0, curr=1: 0 1 2 3 4 -> 0 2 1 3 4 -> 0 3 2 1 4 

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0), prev = dummy, curr = head, next;
        dummy.next = head;
        int length = 0;
        while(head != null) {
            length++;
            head = head.next;
        }
        head = dummy.next;
        for(int i = 0; i < length / k; i++) {
            for(int j = 0; j < k - 1; j++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
            curr = prev.next;
        }
        return dummy.next;
    }
}

SUMMARY

学习通过构造头节点来简化代码，反转链表可使用头插法，也可使用直接反转。