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

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

正文


题目


1.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


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


时间复杂度:只需要遍历一次链表,所以时间复杂度为图片说明。

空间复杂度:需要额外常数级别的内存空间,所以空间复杂度为图片说明


相关文章
|
3月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
|
3月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
33 0
|
3月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
27 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
3月前
【刷题记录】链表的回文结构
【刷题记录】链表的回文结构
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
52 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
41 4
|
3月前
|
存储 Python
【Leetcode刷题Python】23. 合并K个升序链表
合并K个升序链表的方法:使用数组排序的暴力求解法、使用小顶堆的高效方法,以及分而治之的策略,并提供了相应的Python实现代码。
19 1
|
3月前
|
机器学习/深度学习
【刷题记录】相交链表
【刷题记录】相交链表
|
3月前
【刷题记录】链表的中间结点
【刷题记录】链表的中间结点
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表