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

旧城等待， 2023-10-04 17:37 20阅读 0赞

### 描述 ###

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表  
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样  
你不能更改节点中的值，只能更改节点本身。

数据范围： \\ 0 \\le n \\le 2000 0≤n≤2000 ， 1 \\le k \\le 20001≤k≤2000 ，链表中每个元素都满足 0 \\le val \\le 10000≤val≤1000  
要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如：

给定的链表是1→2→3→4→5

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

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

### 示例1 ###

输入：

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

返回值：

{2,1,4,3,5}

### 示例2 ###

输入：

{},1

返回值：

{}

**方法1代码：**

/**
     * struct ListNode {
     *	int val;
     *	struct ListNode *next;
     * };
     *
     * C语言声明定义全局变量请加上static，防止重复定义
     */
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
        // write code here
        int len=0;
        struct ListNode * p=NULL;
        struct ListNode *r=p;
        struct ListNode* temp=head;
        struct ListNode *pre=NULL;
        struct ListNode *cur= malloc(0) ;
        int i=1;
        if(head==NULL||head->next==NULL||k==1){
            return head;
        }
        else{
            while(temp){
                temp=temp->next;
                len++;
            }
            if(len<k)  return head;  //如果k大于长度则直接返回
            temp=head;  //就是翻转后的尾结点
            int s=len%k;
            int l=len/k;
            for(i=1;i<=l;i++){
                p=NULL;
                for(int j=1;j<=k;j++){ 
                    r=temp->next;
                    temp->next=p;
                    p=temp;  //p是翻转后的头结点2,1  ->4,3
                    temp=r;  //temp翻转后的尾结点的下一个节点3,4,5  ->5
                }
                 cur->next=p;   //cur始终是每一次翻转后段落的头结点的前驱节点，用来连接当前翻转后的段落
                 if(i==1){
                     head=p;   //当属于第一段翻转时
                 }
                 while(cur->next!=NULL)   cur=cur->next;   //找到翻转后段落的最后的节点
             }
             cur->next=temp;   //不足k的段落，当前cur为翻转后段落的最后的节点，temp为不足k的段落的头结点
        }
    }
    
    
    
    //或者不增加记录翻转后的头结点的前驱节点，直接用头结点遍历来找到翻转后的头结点的前驱节点
    //如下代码
    struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
        // write code here
        int len=0;
        struct ListNode * p=NULL;
        struct ListNode *r=p;
        struct ListNode* temp=head;
        struct ListNode *pre=NULL;
        struct ListNode *cur= malloc(0) ;
        int i=1;
        if(head==NULL||head->next==NULL||k==1){
            return head;
        }
        else{
            while(temp){
                temp=temp->next;
                len++;
            }
            if(len<k)  return head;  //如果k大于长度则直接返回
            temp=head;  //就是翻转后的尾结点
            int s=len%k;
            int l=len/k;
            for(i=1;i<=l;i++){
                p=NULL;
                for(int j=1;j<=k;j++){ 
                    r=temp->next;
                    temp->next=p;
                    p=temp;  //p是翻转后的头结点2,1  ->4,3
                    temp=r;  //temp翻转后的尾结点的下一个节点3,4,5  ->5
                }
    //             cur->next=p;   //cur始终是每一次翻转后段落的头结点的前驱节点，用来连接当前翻转后的段落
    //             if(i==1){
    //                 head=p;   //当属于第一段翻转时
    //             }
    //             while(cur->next!=NULL)   cur=cur->next;   //找到翻转后段落的最后的节点
    //         }
    //         cur->next=temp;
                if(i==1){
                    head=p;
                    while(p->next){
                        p=p->next;
                    }
                    pre=p;  //找到翻转后的最后的节点
                }
                else{
                    pre->next=p;  //前面的翻转后的段落的最后个节点与当前翻转后段落的第一个节点相连接
                     while(p->next){
                        p=p->next;
                    }
                    pre=p;  //找到翻转后的最后的节点
                }
            }
            pre->next=temp;
            return head;
       }
    }

**方法2：递归调用：**

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param head ListNode类 
         * @param k int整型 
         * @return ListNode类
         */
        public ListNode reverse(ListNode a,ListNode b){   //左闭右开 【a,b)
            ListNode pre=null;
            ListNode nxt=null;
            if(a==b){
                return a;
            }
            while(a!=b){
                nxt=a.next;
                a.next=pre;
                pre=a;
                a=nxt;
            }
            
            return pre;
        }
            
        
        public ListNode reverseKGroup (ListNode head, int k) {
            int len;
            ListNode cur=head;
            for(int i=0;i<k;i++){
                if(cur==null){  //如果当前段落只剩下不足k个时
                    return head;   //直接返回当前段落的头结点，则该段落不翻转
                }  
                cur=cur.next;
            }
            ListNode ph=reverse(head,cur);   //这是翻转后的头结点
            //head节点就是第一个翻转段的尾结点
            head.next=reverseKGroup(cur,k);   //递归调用翻转，第一个翻转段的尾结点，连接第二个翻转段的头结点
            return ph;
        }
    }