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

题目描述

将给出的链表中的节点每\ k k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是\ k k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 \ O(1) O(1)

例如：

给定的链表是1\to2\to3\to4\to51→2→3→4→5

对于 \ k = 2 k=2, 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5

对于 \ k = 3 k=3, 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5

示例1

输入

复制

{1,2,3,4,5},2

返回值

复制

{2,1,4,3,5}

循环翻转

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) {
        // k小于2的时候不用翻转
        if(k<2)return head;        
        ListNode dummyNode=new ListNode(0);        
        ListNode pre=dummyNode;
        pre.next=head;
        // 遍历一次求出链表的长度
        int len=0;
        ListNode temp=head;
        while(temp!=null){
            len++;
            temp=temp.next;
        }
        // 遍历k组
        for(int i=0;i<len/k;i++){
            // 对于每个组内翻转k-1次就交换完了
            for(int j=1;j<k;j++){
                ListNode nex=head.next;
                if(nex==null)break;
                head.next=nex.next;
                nex.next=pre.next;
                pre.next=nex;
            }
            // 将交换的起点的pre设为当前的节点
            pre=head;
            // 将当前节点切换到下一个节点
            head=head.next;
        }
        return dummyNode.next;
    }
}

赏

谢谢你请我吃糖果

微信