【牛客刷题】链表的奇偶重排

小灰灰 2024-05-06 09:44 128阅读 0赞

#### 文章目录 ####

*  题目
 *   *  题意整理
     *  方法一（转化为数组）
     *   *  1.解题思路
         *  2.代码实现
         *  3.复杂度分析
     *  方法二（原地拆分再合并）
     *   *  1.解题思路
         *  2.代码实现
         *  3.复杂度分析
         *  4.提交代码

> ?每日推荐
> 
> ?文章开始之前我想首先介绍一下[牛客][Link 1]，以便没有使用过的小伙伴能够快速入手，[牛客网][Link 1]是国内最大的算法、面试、招聘网站，涵盖了多种大厂面试真题以及题解，里面大佬云集，各种题目的解决方案层出不穷，绝对能让你大开眼界，而且[牛客][Link 1]是你在人生中不同的阶段都能对你有所帮助的编程软件（完全免费），如果感兴趣可以访问注册一下
> 
> 访问链接：[牛客-国内最大的刷题网站][Link 1]

## 题目 ##

![在这里插入图片描述][bcf20c1eb8904044afd4f7ce805138ad.png]

### 题意整理 ###

*  给定一个链表。
 *  链表的奇数位、偶数位索引节点分别连在一起，重排成一个新的链表。

### 方法一（转化为数组） ###

#### 1.解题思路 ####

比较容易实现的方法是先将链表转化为数组，然后分别将奇数、偶数索引对应的值构造成对应的奇偶链表。最后再将奇链表和偶链表拼接起来。

#### 2.代码实现 ####

import java.util.*;
     
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     *   public ListNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
     
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param head ListNode类
         * @return ListNode类
         */
        public ListNode oddEvenList (ListNode head) {
        
            //特殊情况判断
            if(head==null||head.next==null) return head;
     
            // 计算链表长度
            int len=0;
            ListNode cur=head;
            while(cur!=null){
        
                cur=cur.next;
                len++;
            }
     
            //转换为数组
            int[] arr=new int[len];
            int id=0;
            cur=head;
            while(cur!=null){
        
                arr[id++]=cur.val;
                cur=cur.next;
            }
     
            //数组转化为奇偶链表，并连接在一起
            ListNode oddCur=new ListNode(arr[0]);
            ListNode evenCur=new ListNode(arr[1]);
            ListNode oddHead=oddCur;
            ListNode evenHead=evenCur;
            for(int i=2;i<arr.length;i++){
        
                if(i%2==0){
        
                    oddCur.next=new ListNode(arr[i]);
                    oddCur=oddCur.next;
                }
                else{
        
                    evenCur.next=new ListNode(arr[i]);
                    evenCur=evenCur.next;
                }
            }
            //拼接
            oddCur.next=evenHead;
            return oddHead;
     
        }
    }

#### 3.复杂度分析 ####

时间复杂度：需要遍历两次链表和一次数组，所以时间复杂度为图片说明 。  
空间复杂度：需要额外长度为n的数组存储元素，所以空间复杂度为图片说明。

### 方法二（原地拆分再合并） ###

#### 1.解题思路 ####

核心思路是遍历链表，每次记录当前节点的下一个节点，然后将当前节点指向下一个节点的后一位，之后指针移动到之前保留的下一个节点处。  
主要步骤：

*  判断链表为空或只有一个节点的情况
 *  初始化偶链表头指针、当前节点、奇链表最后停留的节点
 *  遍历链表，拆分为奇偶链表，并记录长度
 *  根据长度判断奇链表最后一个节点，合并奇偶链表

动图展示：  
![在这里插入图片描述][28645349278a436e88eb891d7b93f519.gif_pic_center]

#### 2.代码实现 ####

import java.util.*;
     
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     *   public ListNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
     
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param head ListNode类
         * @return ListNode类
         */
        public ListNode oddEvenList (ListNode head) {
        
            //特殊情况判断
            if(head==null||head.next==null) return head;
     
            //初始化
            ListNode evenHead=head.next;
            ListNode cur=head;
            ListNode oddTail1=null,oddTail2=null;
     
            //拆分为奇偶链表，并记录长度
            int len=1;
            while(cur.next!=null){
        
                len++;
                oddTail1=cur.next;
                oddTail2=cur;
     
                //保留下一个节点
                ListNode next=cur.next;
                //拆分
                cur.next=cur.next.next;
                //指针后移到下一个节点
                cur=next;
            }
     
            //如果原链表长度是奇数，则链表最后一个节点是奇数链表尾节点
            if(len%2==1){
        
                //合并
                oddTail1.next=evenHead;
            }
            //如果原链表长度是偶数，则链表倒数第二个节点是奇数链表尾节点
            else{
        
                //合并
                oddTail2.next=evenHead;
            }
            return head;
     
        }
    }

#### 3.复杂度分析 ####

时间复杂度：只需要遍历一次链表，所以时间复杂度为图片说明。  
空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为图片说明

#### 4.提交代码 ####

![在这里插入图片描述][803232d3dfcb44969ecff66d375aa305.png]

> ?每日推荐
> 
> 访问链接：[牛客-国内最大的刷题网站][Link 1]

[Link 1]: https://www.nowcoder.com/exam/oj?page=1&tab=SQL%E7%AF%87&topicId=199&fromPut=pc_csdncpt_ddssyx_sql
[bcf20c1eb8904044afd4f7ce805138ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/d38f0bea277e4819b942512fab259647.png
[28645349278a436e88eb891d7b93f519.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/713fa73245b7430da004ffd5436d1b5a.gif
[803232d3dfcb44969ecff66d375aa305.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/e88f716171f14dbc960246a5914faa1c.png