🍍每日推荐
🍖文章开始之前我想首先介绍一下牛客，以便没有使用过的小伙伴能够快速入手，牛客网是国内最大的算法、面试、招聘网站，涵盖了多种大厂面试真题以及题解，里面大佬云集，各种题目的解决方案层出不穷，绝对能让你大开眼界，而且牛客是你在人生中不同的阶段都能对你有所帮助的编程软件（完全免费），如果感兴趣可以访问注册一下
访问链接：牛客-国内最大的刷题网站
题目
题意整理
- 给定一个链表。
- 链表的奇数位、偶数位索引节点分别连在一起，重排成一个新的链表。
方法一（转化为数组）
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.复杂度分析
时间复杂度：只需要遍历一次链表，所以时间复杂度为图片说明。
空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为图片说明
4.提交代码
🍍每日推荐
访问链接：牛客-国内最大的刷题网站