链表中的节点每k个一组翻转

import java.util.*;

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

import java.util.*;
public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        //找到每次翻转的尾部
        ListNode tail = head;
        //遍历k次到尾部 
        for(int i = 0; i < k; i++){ 
            //如果不足k到了链表尾，直接返回，不翻转
            if(tail == null) 
                return head;
            tail = tail.next; 
        }
        //翻转时需要的前序和当前节点
        ListNode pre = null; 
        ListNode cur = head;
        //在到达当前段尾节点前
        while(cur != tail){ 
            //翻转
            ListNode temp = cur.next; 
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //当前尾指向下一段要翻转的链表
        head.next = reverseKGroup(tail, k); 
        return pre;
    }
}

        if(head == null || head.next == null || k<2)return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head, pre = dummy, temp = cur;
        while(true)
        {
            //判断是否可分组
            for(int i=0;i<k;i++)
            {
                if(temp == null) return dummy.next;
                temp= temp.next;
            }

            //倒插法
            for(int i = 1; i<k;i++)
            {
                 temp = cur.next;
                 cur.next = temp.next;
                 temp.next = pre.next;
                 pre.next = temp;
            }

            //置位
            pre = cur;
            cur = pre.next;
            temp = cur;
        }

public class Solution {

    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 长度
        int n = 0;
        ListNode cur = head;
        while( cur != null ) {
            n ++;
            cur = cur.next;
        }

        // 已反转 + 未反转
        int remain = n;
        ListNode pre = null, nxt = null, last = dummy;  // last: 已反转的末尾
        cur = head;
        while ( remain >= k ) {
            remain -= k;

            // 反转 k 
            for (int i = 0; i < k; i++) {
                nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }

            // 接上前面
            nxt = last.next;    // 当前反转前的head, 也就是反转后的 tail
            last.next = pre;    //pre: 反转后的head

            // 接上后面
            last = nxt;
            last.next = cur;     // cur: 下一组待反转的 head
        }
        return dummy.next;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(head==null){
            return head;
        }
        ArrayList<Integer> list=new ArrayList<>();
        Stack<Integer> stack=new Stack<>();
        ListNode tmpList=head;
        while(tmpList!=null){
            list.add(tmpList.val);
            tmpList=tmpList.next;
        }
        if(k>list.size()){
            return head;
        }
        ArrayList<Integer> result=new ArrayList<>();
        for(int i=0;i<list.size();i++){
            stack.push(list.get(i));
            if((i+1)%k==0){
                while(!stack.isEmpty()){
                    result.add(stack.pop());
                }
            }
        }
        ArrayList<Integer> tmp=new ArrayList<>();
        while(!stack.isEmpty()){
            tmp.add(stack.pop());
        }
        Collections.reverse(tmp);
        result.addAll(tmp);
        ListNode tmpNode=new ListNode(result.get(0));
        ListNode returnList=tmpNode;
        for(int i=1;i<result.size();i++){
            ListNode node=new ListNode(result.get(i));
            tmpNode.next=node;
            tmpNode=tmpNode.next;
        }
        return returnList;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        int len=0;
        ListNode cur=head;
        while(cur!=null){
            len++;
            cur=cur.next;
        }
        // //res用于保存最终结果
        // ListNode res=new ListNode(-1);
        // ListNode tail=res;
        // ListNode p=head;
        // while(len>=k){
        //     len=len-k;
        //     ListNode s=null;
        //     for(int i=1;i<=k;i++){
        //         ListNode tmp=p.next;
        //         p.next=s;
        //         s=p;
        //         p=tmp;
        //     }
        //     //反转完，s拼接到tail后
        //     tail.next=s;
        //     //tail指针移动到最后
        //     ListNode ss=s;
        //     while(ss.next!=null){
        //         ss=ss.next;
        //     }
        //     tail=ss;
        // }
        // //不够k个的节点拼接到tail后
        // if(p!=null){
        //     tail.next=p;
        // }
        // return res.next;

        //res用于保存最终结果
        ListNode res = new ListNode(-1);
        ListNode tail=res;
        ListNode p=head;
        Stack<ListNode> stack = new Stack<>();
        while (len >= k) {
            len = len - k;
            for (int i = 0; i < k; i++) {
                stack.push(p);
                p=p.next;
            }
            for(int i=0;i<k;i++){
                ListNode node=stack.pop();
                tail.next=node;
                node.next=null;
                tail=node;
            }
        }
        tail.next=p;
        return res.next;
    }
}

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1) {
            return head;
        }
        ListNode p = new ListNode(0);


        p.next = head;
        // write code here
        int m = 1;

        //每次翻转开始结点的前一个结点
        ListNode prePre = p;

        //开始翻转的结点
        ListNode pre = null;
        //结束结点
        ListNode end = null;


        ListNode a = head;

        //计算长度
        int size = 0;
        while (a != null) {
            size++;
            a = a.next;
        }


        a = head;

        int i = 0;
        while (i < size && a != null) {

            //找到翻转起点
            if (m % k == 1) {
                pre = a;
            }
            //找到翻转终点
            if (m % k == 0) {
                end = a;
            }
            //开始翻转
            if (pre != null && end != null) {

                ListNode curr = pre;
                ListNode prec = end.next;
                ListNode endEnd = end.next;

                //结点进入 终点的下一个结点就结束
                while (curr != endEnd) {
                    ListNode tmp = curr.next;
                    curr.next = prec;
                    prec = curr;
                    curr = tmp;
                }

                //结束的时候，翻转开始结点需要执行 翻转终点
                prePre.next = prec;

                //下一个开始结点的前一个结点
                prePre = pre;
                a = pre;

                pre = null;
                end = null;

            }
            a = a.next;
            i++;
            m++;
        }

        return p.next;
    }

public ListNode reverseKGroup (ListNode head, int k) {
        ListNode tail=head;//tail为分组界限
        for(int i=0;i<k;i++){   //如果不足k个
            if(tail==null) return head;
            tail=tail.next;
        }
        //如果足k个,反转链表
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=tail){//因为下一段的头是tail
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        head.next=reverseKGroup(tail,k);
        return pre;
    }

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if (head == null){
            return null;
        }
        //len记录链表长度
        int len = 0;
        //eg用于遍历链表
        ListNode eg = head;
        while (eg != null){
             len++;
             eg = eg.next;
        }
        if (len < k){
        //如果长度小于k,返回当前链表
            return head;
        }
        int num = len / k;
        //ListNode用于标记每一组的第一个节点
        ListNode headeg = head;
        //eg用于记录每一组翻转后的最后一个节点
        eg = head;
        for (int i = 1; i <= num; i++){
        //为每一组的翻转做准备工作
            ListNode eg0 = headeg;
            ListNode eg1 = headeg.next;
            headeg.next = null;
            int egi = k;
            while(egi - 1!= 0){
            //对每一组进行翻转
                egi--;
                ListNode eg2 = eg1.next;
                eg1.next = headeg;
                headeg = eg1;
                eg1 = eg2;
            }
            if (i == 1){
   //移动头节点,使其指向翻转后的第一个节点,只能在第一次翻转时执行一次
                head = headeg;
            }else{
       //连接翻转后的前一组与翻转后的当前组
                eg.next = headeg;
                eg = eg0;
            }
            //连接翻转后的当前组与下一组
            eg0.next = eg1;
            //使headeg始终指向下一组的头节点
            headeg = eg1;
        }
       return head;
    }