题解 | #链表中的节点每k个一组翻转#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        //思路：一个栈即可，每次k个元素入栈，如果不够k说明已经到了最后一部分
        if(head==null)return null;
        if(k==1)return head;
        Stack<ListNode>stack=new Stack<>();
        Stack<ListNode>stack2=new Stack<>();
        int i=1;
        ListNode cur=head,pre=null;
        ListNode partTail=null;//记录每一部分的最后一个元素
        //循环结束的标志,cur==null
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
            //第一部分，简单翻转
            if(i==k){
                ListNode cur1=stack.pop();
                head=cur1;
                //出栈
                while(!stack.isEmpty()){
                    cur1.next=stack.pop();
                    cur1=cur1.next;
                }
                //记录本部分最后一个元素
                partTail=cur1;   
            }else if(i%k==0){
                //栈中元素数已经到了k个
                //出栈，连接构造反向链表
                ListNode cur1=stack.pop();
                //此时该部分的首元素为cur1
                //将上一部分的尾元素连接到cur1
                partTail.next=cur1;
                //循环出栈
                while(!stack.isEmpty()){
                    cur1.next=stack.pop();
                    cur1=cur1.next;
                }
                //记录本部分最后一个元素
                partTail=cur1;
            }
            i++;
        }
        //while循环中i多加了一个1，需要结束后减去他
        i--;
        //如果k比链表长，则整个链表都属于最后一部分不用翻转
        if(k>i)return head;
        //如果k=i，说明只有第一部分，只需要将末尾元素next填null即可
        if(k==i){
            partTail.next=null;
            return head;
        }
        //只有i不能被k整除时才有最后一部分
        if(i%k!=0){
            //如果栈中有元素,说明k不能被链表长度整除,还残留最后一部分链表
            //这一部分不翻转
            while(!stack.isEmpty()){
                cur=stack.pop();
                stack2.push(cur);
            }
            partTail.next=cur;
            while(!stack2.isEmpty()){
                cur.next=stack2.pop();
                cur=cur.next;
            }
            cur.next=null;
        }
        return head;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        //思路：递归
        //终止条件：访问到null元素，此时有若干情况：
        //1、k>length，说明只有最后一部分，不用变，直接return head
        //2、k==length，说明只有第一部分，翻转返回即可
        //3、k<length，说明有多部分，递归
        ListNode partTail=null;//每一部分的尾就是原链表的头
        ListNode cur=head;
        for(int i=1;i<=k;i++){
            //如果在i在到k的过程中就访问到了null元素
            //说明k>length，符合情况1
            if(cur==null) return head;
            cur=cur.next;
        }
        partTail=cur;
        //翻转需要记录pre和next节点
        ListNode pre=null,next;
        cur=head;
        while(cur!=partTail){
            
            next=cur.next;
            cur.next=pre; 
            pre=cur;
            cur=next;      
        }
        
        //当前尾指向下一段要翻转的链表
        head.next=reverseKGroup(partTail,k);
        return pre;
    }
}