(链表专题) 328. 奇偶链表 ——【Leetcode每日一题】

328. 奇偶链表

给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。

第一个 节点的索引被认为是 奇数第二个 节点的索引为 偶数 ,以此类推。

请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例 1:

在这里插入图片描述

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

示例 2:

在这里插入图片描述

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

提示:

  • n == 链表中的节点数
  • 0 < = n < = 1 0 4 0 <= n <= 10^4 0<=n<=104
  • − 1 0 6 < = N o d e . v a l < = 1 0 6 -10^6 <= Node.val <= 10^6 106<=Node.val<=106

思路:

  • 分别定义奇偶链表,头节点分别为:headhead2
  • 再定义两个节点 odd , even 分别定义指向奇链表和偶链表最后一个节点
  • 遍历原链表,将当前结点 交替 插入到奇链表和偶链表(尾插法);
  • 将偶链表拼接在奇链表后面。

代码:(Java、C++)

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode head2 = head.next;//偶链表头节点
        ListNode odd = head, even = head2;//分别定义指向奇链表和偶链表最后一个节点
        while(even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = head2;
        return head; 
    }
}

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* head2 = head->next;//偶链表头节点
        ListNode* odd = head, *even = head2;//分别定义指向奇链表和偶链表最后一个节点
        while(even != NULL && even->next != NULL){
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = head2;
        return head; 
    }
};

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 是链表的节点数。需要遍历链表中的每个节点,并更新指针。
  • 空间复杂度 O ( 1 ) O(1) O(1)。只需要维护有限的指针。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/11828.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

腾讯云轻量应用服务器搭建网站教程(WordPress为例)

腾讯云轻量应用服务器搭建WordPress网站教程&#xff0c;先安装WordPress应用镜像&#xff0c;然后远程连接轻量应用服务器获取WP用户名和密码&#xff0c;域名DNS解析到轻量服务器IP地址&#xff0c;登陆WordPress后台管理全过程&#xff0c;腾讯云百科来详细说下腾讯云轻量服…

弹塑性力学--应变硬化

在单轴拉伸试验中&#xff0c;当应力超过屈服强度后&#xff0c;需要施加更大的载荷产生更大的应力&#xff0c;才会使材料发生更多的塑性变形。随着塑性应变的增加&#xff0c;材料变得更强、更难以变形了&#xff0c;因此这个阶段称为“应变硬化”&#xff08;Strain Hardeni…

Vue语法糖<script setup>详解,用最快的方式让你看懂和<script>的区别

前言 Vue3出来已经3年了&#xff0c;但是前两天在百度上搜索有关setup语法糖的细节时&#xff0c;发现很多博客关于语法糖细节部分&#xff0c;还是讲的很粗糙&#xff0c;因此决定自己来写一篇入门的博客&#xff0c;方便大家快速上手。 <script setup>简介 它是Vue3…

项目沟通管理流程的6大规范步骤

1、建立沟通计划 需要对整个项目的沟通对象、沟通内容、沟通频率、沟通方法等各方面&#xff0c;进行计划和安排。尤其需明确沟通机制&#xff0c;建立完整的沟通计划。并根据项目沟通的具体情况&#xff0c;实时添加和修订计划&#xff0c;以保证沟通管理计划的持续适用性。 项…

拐点!智能座舱破局2023

“这是我们看到的整个座舱域控渗透率&#xff0c;2022年是8.28%&#xff0c;主力的搭载车型仍然是30-35万区间。”3月29日&#xff0c;2023年度&#xff08;第五届&#xff09;高工智能汽车市场峰会上&#xff0c;高工智能汽车研究院首发《2022-2025年中国智能汽车产业链市场数…

每日学术速递4.11

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV 1.InstantBooth: Personalized Text-to-Image Generation without Test-Time Finetuning 标题&#xff1a;InstantBooth&#xff1a;无需测试时间微调的个性化文本到图像生成 作者&a…

HTTP HTTPS简介

一篇文章带你走进HTTP HTTPS场景复现核心干货HTTP/HTTPS简介&#xff08;简单比较&#xff09;HTTP工作原理HTTPS作用场景复现 最近在对前端的深入学习过程中&#xff0c;接触到了与网络请求相关的内容&#xff0c;于是打算出一个专栏&#xff0c;从HTTP与HTTPS入手&#xff0…

基于t-SNE的Digits数据集降维与可视化

基于t-SNE的Digits数据集降维与可视化 描述 t-SNE(t-分布随机邻域嵌入)是一种基于流形学习的非线性降维算法&#xff0c;非常适用于将高维数据降维到2维或者3维&#xff0c;进行可视化观察。t-SNE被认为是效果最好的数据降维算法之一&#xff0c;缺点是计算复杂度高、占用内存…

运行时内存数据区之程序计数器

内存是非常重要的系统资源&#xff0c;是硬盘和CPU的中间仓库及桥梁&#xff0c;承载着操作系统和应用程序的实时选行。JVM内存布局规定了Java在运行过程中内存申请、分配、管理的策略&#xff0c;保证了JVM的高效稳定运行。 不同的VM对于内存的划分方式和管理机制存在着部分差…

英特尔CEO基辛格:开创可持续计算新时代

近日&#xff0c;帕特基辛格作为英特尔CEO后&#xff0c;第一次来华访问。在2023英特尔可持续发展高峰论坛上&#xff0c;笔者有幸聆听他的演讲。他严谨又不乏幽默地给我们分享了英特尔如何践行可持续发展的思考和举措。 基辛格表示&#xff0c;身处科技行业&#xff0c;我们不…

DeepFM论文翻译

1.摘要 为了最大化推荐系统的CTR&#xff0c;学习用户行为的复杂交叉特征很关键。 尽管有很大进步&#xff0c;现有的方法无论对低阶还是高阶的交叉特征&#xff0c;似乎还是有很强的bias, 或者需要专门的特征工程。 本文&#xff0c;我们证明了得出一个能强化高阶和低阶交叉特…

钢网是SMT生产使用的一种工具,如何制作?

钢网是SMT生产使用的一种工具&#xff0c;其主要功能是将锡膏准确地涂敷在有需要焊接的PCB焊盘上。 钢网的好坏&#xff0c;直接影响印刷工作的质量&#xff0c;目前一般使用的金属钢网&#xff0c;是由薄薄的、带有小孔的金属板制作成的&#xff0c;在开孔处&#xff0c;锡膏…

记录网关zuul处理跨域/XSS问题

一&#xff0c;疑问 1.之前遇到跨域问题是在NG中解决的&#xff0c;添加跨域请求头和域名配置。那么与网关处理跨域问题关系是什么&#xff0c;NG处理了&#xff0c;为什么还需要在网关中处理 二&#xff0c;前置知识 zuul概念与原理 zuul 的概念和原理 - 知乎 Zuul工作原…

全球首个完全开源的指令跟随大模型;T5到GPT-4最全盘点

1. Dolly 2.0&#xff1a;世界上第一个完全开源的指令跟随LLM 两周前&#xff0c;Databricks发布了类ChatGPT的大型语言模型 (LLM)Dolly&#xff0c;其训练成本不到 30 美元。今天&#xff0c;他们发布了 Dolly 2.0&#xff0c;这是业内第一个开源的指令跟随LLM&#xff0c;并根…

gdb 跟踪调式core

自己编译的问题出现段错误: 编译:使用gdb调试core文件来查找程序中出现段错误的位置时,要注意的是可执行程序在编译的时候需要加上-g编译命令选项。 gdb调试core文件的步骤 gdb调试core文件的步骤常见的有如下几种,推荐第一种。 具体步骤一: (1)启动gdb,进入core文…

Midjourney详细注册和使用教程

来源&#xff1a;Midjoureny详细注册使用教程【探索ChatGPT】 Midjourney&#xff0c;用户只需要输入一段图片的文字描述&#xff0c;即可生成精美的绘画&#xff0c;相信了解Midjourey的小伙伴已经对它强大之处而赞叹&#xff01; 下面是用通俗易懂的步骤教会大家如何注册和…

企业网站架构部署与优化

系列文章目录 文章目录系列文章目录一、LAMP概述与简介1.LAMP2.各组件的主要作用如下&#xff1a;二、1.编译安装Apache http服务2.编译安装 Mysql 服务3.编译安装 PHP 解析环境总结一、LAMP概述与简介 1.LAMP LAMP架构是目前成熟的企业网站应用模式之一&#xff0c;指的是协…

Linux内核之网络协议栈以及套接字sk_buff分析

网络协议栈以及套接字sk_buff分析一、Linux 内核网络协议栈构架二、网络协议栈常见的数据结构2.1、TCP/IP 参考模型及 ISO/OSI 参考模型2.2、套接字 sk_buff 分析2.3、套接字缓冲区管理数据2.4、Linux 内核提供套接字缓冲区标准 API 函数2.5、使用一个表头来实现套接字缓冲区的…

Scala - 时间工具类 LocalDateTime 常用方法整理

目录 一.引言 二.LocalDateTime 获取与格式化 1.获取当前时间 LocalDateTime 2.根据时间戳获取 LocalDateTime 3.指定时间获取 LocalDataTime 4.LocalDataTime 格式化 三.LocalDateTime 读取时间细节 1.获取年-Year 2.获取月-Month 3.获取日-Day 4.获取时-Hour 5.获…

一文读懂域名注册

本文深入浅出讲解域名的注册、建站和管理&#xff0c;通过文章可以了解以下问题&#xff1a; 域名注册及建站流程&#xff1b;域名注册的技术原理&#xff1b;域名管理&#xff08;修改 DNS 服务器、转入转出、自定义 DNSHost、whois 信息&#xff09;。 众所周知&#xff0c;…
最新文章