将单链表的每K个节点之间逆序

将单链表的每K个节点之间逆序

题目：将单链表的每K个节点之间逆序

《程序员代码面试指南》第22题 P74 难度：尉★★☆☆

本题依旧有两种解法。。

首先，需要判断K的值是否小于2，是则不用进行任何调整。同时，最后一组节点数不足K的话，最后一组无需进行逆序调整。

第一种还是利用栈（栈的用处也真的多啊），从左到右遍历链表，不断将节点压入栈。

当栈的大小达到K时，则开始执行逆序操作，不断的将节点从栈顶弹出。同时需注意与上一组最后一个节点以及下一组第一个节点之间的连接。

此外，第一组节点还需额外注意，将第一组的最后一个节点作为链表的新头结点，最后需将其返回。

书中代码如下：

public Node reverseKNodes1(Node head, int K) {
    if (K < 2) {
      	return head;
    }
    Stack stack = new Stack();
    Node newHead = head;
    Node cur = head;
    Node pre = null;
    Node next = null;
    while (cur != null) {
        next = cur.next;
        stack.push(cur);
        if (stack.size() == K) {
            pre = resign1(stack, pre, next);
            newHead = newHead == head ? cur : newHead;
        }
        cur = next;
    }
    return newHead;
}

public Node resign1(Stack stack, Node left, Node right) {
    Node cur = stack.pop();
    if (left != null) {
      	left.next = cur;
    }
    Node next = null;
    while (!stack.isEmpty()) {
        next = stack.pop();
        cur.next = next;
        cur = next;
    }
    cur.next = right;
    return cur;
}

显然第一种解法的额外空间复杂度为O(N)，于是还有为O(1)的第二种解法，即直接在原链表中调整。

用变量记录每一组开始的第一个节点和最后一个节点，直接逆序调整，同时注意与之前组的最后一个节点以及下一组的第一个节点之间的连接。

另外也需要注意第一组节点的特殊处理。

具体代码如下：

public Node reverseKNodes2(Node head, int K) {
    if (K < 2) {
      	return head;
    }
    Node cur = head;
    Node start = null;
    Node pre = null;
    Node next = null;
    int count = 1;
    while (cur != null) {
        next = cur.next;
        if (count == K) {
            start = pre == null ? head : pre.next;
            head = pre == null ? cur : head;
            resign2(pre, start, cur, next);
            pre = start;
            count = 0;
        }
      count++;
      cur = next;
    }
    return head;
}

public void resign2(Node left, Node start, Node end, Node right) {
    Node pre = start;
    Node cur = start.next;
    Node next = null;
    while (cur != right) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    if (left != null) {
      	left.next = end;
    }
    start.next = right;
}