题解 | #链表的奇偶重排#

题意整理

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

方法一（转化为数组）

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.解题思路

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

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

动图展示：

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.复杂度分析

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