正文
题目
题意整理
给定一个链表。
链表的奇数位、偶数位索引节点分别连在一起，重排成一个新的链表。
方法一（转化为数组）
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.复杂度分析
时间复杂度：只需要遍历一次链表，所以时间复杂度为图片说明。
空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为图片说明
