【链表】打卡9：将单链表的每K个结点之间逆序

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

【题目描述】

给定一个单链表的头结点head, 实现一个调整单链表的函数，使得每K个结点之间逆序，如果最后不够K个结点一组，则不调整最后几个结点。

例如：

链表:1->2->3->4->5->6->7->8->null, K = 3。

调整后：3->2->1->6->5->4->7->8->null。其中 7，8不调整，因为不够一组。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉：★★☆☆

解答

对于这道题，如果你不知道怎么逆序一个单链表，那么可以看一下我之前写的【链表问题】如何优雅着反转单链表

这道题我们可以用递归来实现，假设方法reverseKNode()的功能是将单链表的每K个结点之间逆序。reverse()方法的功能是将一个单链表逆序。

那么对于下面的这个单链表，其中 K = 3。

我们把前K个结点与后面的结点分割出来：

temp指向的剩余的链表，可以说是原问题的一个子问题。我们可以调用reverseKNode()方法将temp指向的链表每K个结点之间进行逆序。再调用reverse()方法把head指向的那3个结点进行逆序，结果如下：

接着，我们只需要把这两部分给连接起来就可以了。最后的结果如下：

如果不大理解，看下代码可能就比较好理解了。

代码如下

//每k个结点为一组的逆转
public static Node reverseKNodes(Node head, int k) {
    //注意要判断head.next是否为空
    if(head == null || head.next == null){
        return head;
    }
    Node cur = head;
    for (int i = 1;cur != null && i < k; i++) {
        cur = cur.next;
    }
    //判断，没有形成一组则返回	cur == null 或者 i==k
    if(cur == null){
        return head;
    }
    //next指向剩余的链表
    Node next = cur.next;
    //注意这一步要把链表给断开，断开cur其实是断开head，否则会发生StackOverflowError错误
    cur.next = null;
    cur = head;
    //逆转这k个结点
    Node newHead = reverse(cur);
    //把之后的部分链表进行每k个结点逆转
    Node newTemp = reverseKNodes(next,k);
    //把两部分结点连接起来
    cur = newHead;
    while(cur.next!=null){
        cur = cur.next;
    }
    cur.next = newTemp;
    return newHead;
}
//单链表逆序
public static Node reverse(Node head){
    if(head == null || head.next == null){
        return head;
    }
    Node newList = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return newList;
}

当然，这道题一个很简单的做法就是利用栈来辅助，每K个结点入栈就把这K个结点出栈连接成一个链表，之后剩余再在进栈…..

//使用栈
public static Node reverseKNodesUseStack(Node head, int k){
    if(head == null || head.next == null){
        return head;
    }
    ArrayDeque<Node> stack = new ArrayDeque<Node>();
    Node cur = head;
    //stack的push操作比cur指针慢一步
    for (int i = 1; cur!=null&&i<k; i++) {
        stack.push(cur);
        cur=cur.next;
    }
    if(cur == null){
        return head;
    }
    stack.push(cur);

    Node next = cur.next;
    cur.next = null;

    Node newHead = stack.pop();
    cur = newHead;
    while(!stack.isEmpty()){
        cur.next = stack.pop();
        cur = cur.next;
    }
    //可以边push边pop处理链表，但是这样需要两个循环，时间复杂度就上去了。
    Node newTemp = reverseKNodesUseStack(next,k);
    //把两部分结点连接起来
    cur.next = newTemp;
    return newHead;
}

不过这种做法的额外空间复杂度是O(K)。

测试代码

public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7,8};
    Node head = new Node(arr[0]);
    Node node = head;
    int i = 0;
    while(++i<arr.length){
        node.next = new Node(arr[i]);
        node = node.next;
    }
    //node = reverseKNodes(head,8);
    node = reverseKNodesUseStack(head,9);
    while(node!=null){
        System.out.print(node.value+" ");
        node = node.next;
    }
}

问题拓展

思考：如果这是一个环形单链表呢？该如何实现呢？
来源：苦逼的码农（ID:di201805）

（完）