用Java实现LeetCode 25. K 个一组翻转链表

public class Node {
    public final int id;
    public Node pre;
    public Node next;
    public Node(int id) {
        this.id = id;
    }
}

public class LinkedList {

    public Node head;

    public LinkedList(int size) {
        Node pre = null;
        for (int i = 0; i < size; i++) {
            Node n = new Node(i);
            n.pre = pre;
            if (pre != null)
                pre.next = n;
            if (i == 0)
                head = n;
            pre = n;
        }
    }

    public void print() {
        for (Node current = head; current != null; current = current.next) {
            System.out.print(current.id + " ");
        }
    }
}

首先，题目条件里没说链表长度是已知条件，k个一段，有几段是不知道的，只有遍历到一段的尾部你才知道这里有k个结点组成的一段。每发现一段，就从这段的尾部开始往前翻转链表。基本思路就是这样，下面是此题的算法实现。没有参考任何资料，自己花了几个小时写出来的。

private static void reverseKGroup(LinkedList list, int k) {
    Node preSublistTail = null; // 上一段的尾结点
    Node nextSublistHead; // 下一段的头结点
    Node newHead = list.head; // 新的头结点
    Node current = list.head;
    for (int i = 1; current != null; i++) { // 遍历链表并计数
        if (i % k == 0) { // 某一段链表的尾部
            if (i == k) {
                newHead = current; // 新的头结点等于第一段的尾结点
            }
            nextSublistHead = current.next;
            if (preSublistTail != null) {
                preSublistTail.next = current; // 翻转之后，上一段的next就是当前结点了
            }
            // 将这一段链表进行翻转
            Node groupCurrent = current;
            for (int j = k; j > 0; j--) { // 从后往前遍历这一段
                Node next = groupCurrent.pre;
                if (j == k) { // 没翻转前，这一段的尾部
                    groupCurrent.pre = preSublistTail;
                } else {
                    groupCurrent.pre = groupCurrent.next;
                }
                if (j == 1) { // 没翻转前这一段的头部
                    groupCurrent.next = nextSublistHead;
                    // 为进入下一个外循环做准备
                    current = nextSublistHead;
                    preSublistTail = groupCurrent;
                } else {
                    groupCurrent.next = next;
                }
                groupCurrent = next;
            }
        } else {
            current = current.next;
        }
    }
    list.head = newHead;
}

最后附上测试代码：

public static void main(String[] args) {
    LinkedList list = new LinkedList(9);
    list.print();
    System.out.println();
    reverseKGroup(list, 4);
    list.print();
}

因为没有申请额外的内存，所以空间复杂度应该是O(1).

下面简单推一下时间复杂度。假设链表有n个结点，从头往后遍历，每遍历k个结点翻转一段，翻转时需要往前遍历k个结点。所以最坏的情况就是n能被k整除，此时遍历了2n个结点，即时间复杂度是线性阶O(n).
举个例子说明吧，假设n=8，k=4. 遍历到第4个结点时，需要翻转，于是又往回遍历了4个结点，一共遍历了8个。翻转完第一段后又接着第5个结点开始遍历，遍历到第8个结点，又往回遍历4个结点翻转第5到第8个结点，这一段又是遍历8个结点。所以总共是遍历16个结点。上述例子，把n改成9，那就是遍历2*4+2*4+1=17个结点。所以2n是最坏的情况了。