力扣143.重排链表

在这里插入图片描述
通过画图分析,可以从反转后链表与原链表中按顺序各自取一个结点来构建结果,不过要注意的这两个链表只会用到一半,结合 链表的中间结点 和 反转链表 进行解题。

/**
 * 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:
    // 876. 链表的中间结点
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 206. 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    void reorderList(ListNode* head) {
        // 通过画图分析,可以从反转后链表与原链表中按顺序各自取一个结点来构建结果,不过要注意的这两个链表只会用到一半
        // 结合 链表的中间结点 和 反转链表 进行解题

        ListNode* mid = middleNode(head);
        ListNode* head2 = reverseList(mid); // 原链表中间位置后面进行反转

        // 问:循环条件 while head2.next 为什么不能写成 while head2?
        // 答:如果链表长度为偶数,例如链表由 [1,2,3,4,5,6] 组成,那么找中间节点 4 并反转后,我们得到的两个链表分别为
        // head=[1,2,3,4] 和 head2=[6,5,4]。注意它俩都包含节点 4,如果写成 while head2,会导致结果中有两个 4
        // 模拟一下head:
        
        // 第一轮 1->6->2 ->3->4
        // 第二轮:1->6->2->5->3 ->4  得出结果,此时head2->next = nullptr,如果还继续循环,那么会得到1->6->2->5->3->4->4
        while (head2->next) {
            ListNode* tmp = head->next;
            ListNode* tmp2 = head2->next;
            head->next = head2;
            head2->next = tmp;
            head = tmp;
            head2 = tmp2;
        }

    }
};

这道题相当于考察了三道题,包括 求链表中间节点(双指针)和 反转链表(pre)。

关于循环条件 while head2.next 为什么不能写成 while head2?可以看下面这个图:
在这里插入图片描述

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

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

相关文章

nginx在access日志中记录请求头和响应头用作用户身份标识分析

在应用系统中,有时将请求的用户信息和身份认证信息放到请求头中,服务器认证通过后,通过cookie返回客户端一个标识,在后续的请求时,客户端需要带上这个cookie,通过这个cookie,服务器就知道请求的…

如何将数据从 AWS S3 导入到 Elastic Cloud - 第 2 部分:Elastic Agent

作者:来自 Elastic Hemendra Singh Lodhi 了解将数据从 AWS S3 提取到 Elastic Cloud 的不同选项。 这是多部分博客系列的第二部分,探讨了将数据从 AWS S3 提取到 Elastic Cloud 的不同选项。 在本博客中,我们将了解如何使用 Elastic Agent…

【C++】进阶:类相关特性的深入探讨

⭐在对C 中类的6个默认成员函数有了初步了解之后,现在我们进行对类相关特性的深入探讨! 🔥🔥🔥【C】类的默认成员函数:深入剖析与应用(上) 【C】类的默认成员函数:深入剖…

Linux基础知识和常用基础命令

家目录 每个用户账户的专用目录。家目录的概念为用户提供了一个独立的工作空间,它是用户在文件系统中的主要工作区域,包含了用户的个人文件、配置文件和其他数据。 家目录通常位于 /home/用户名 路径下。例如,如果用户名为 1,那…

[Windows] 很火的开源桌面美化工具 Seelen UI v2.0.2

最近,一款来自Github的开源桌面美化工具突然在网上火了起来,引发了大家的关注,不少小伙伴纷纷开始折腾了起来。而折腾的目的,无非是为了一点点乐趣而已,至于结果如何,并不是最要紧的,反倒是体验…

音频声音怎么调大?将音频声音调大的几个简单方法

音频声音怎么调大?在现代生活中,音频内容无处不在,从在线课程和播客到音乐和电影,音频已经成为我们获取信息和娱乐的重要方式。然而,许多人在使用音频时可能会遇到一个常见问题:音频声音太小,无…

组件通信八种方式(vue3)

一、父传子&#xff08;props&#xff09; 关于Props的相关内容可以参考&#xff1a;Props-CSDN博客 父组件通过 props 向子组件传递数据。适合简单的单向数据流。 <!-- Parent.vue --> <template><Child :message"parentMessage" /> </temp…

2018年-2020年 计算机技术专业 程序设计题(算法题)实战_数组回溯法记录图的路径

阶段性总结&#xff1a; 树的DFS存储一条路径采用定义一个栈的形式 图的DFS和BFS&#xff0c;存储一条路径 采用数组回溯法 文章目录 2018年1.c语言程序设计部分2. 数据结构程序设计部分 2019年1.c语言程序设计部分2. 数据结构程序设计部分 2020年1.c语言程序设计部分2. 数据结…

基于微信小程序的智能校园社区服务推荐系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

Kimi 自带的费曼学习器,妈妈再也不用担心我的学习了

大家好&#xff0c;我是Shelly&#xff0c;一个专注于输出AI工具和科技前沿内容的AI应用教练&#xff0c;体验过300款以上的AI应用工具。关注科技及大模型领域对社会的影响10年。关注我一起驾驭AI工具&#xff0c;拥抱AI时代的到来。 AI工具集1&#xff1a;大厂AI工具【共23款…

【经管】比特币与以太坊历史价格数据集(2014.1-2024.5)

一、数据介绍 数据名称&#xff1a;比特币与以太坊历史价格数据集 频率&#xff1a;逐日 时间范围&#xff1a; BTC&#xff1a;2014/9/18-2024/5/1 ETH&#xff1a;2017/11/10-2024/5/1 数据格式&#xff1a;面板数据 二、指标说明 共计7个指标&#xff1a;Date、Open…

安装vue发生异常: idealTree:nodejs: sill idealTree buildDeps

一、异常 C:\>npm install vue -g npm ERR! code CERT_HAS_EXPIRED npm ERR! errno CERT_HAS_EXPIREDnpm ERR! request to https://registry.npm.taobao.org/vue failed, reason: certificate has expired 二、原因 请求 https://registry.npm.taobao.org 失败&#xff0c;证…

通义灵码:融合创新玩法与探索,重塑LeetCode解题策略

文章目录 关于通义灵码安装指南 通义灵码与LeetCode的结合通义灵码给出优化建议通义灵码给出修改建议通义灵码给出自己的思路 总结 大家好&#xff0c;欢迎大家来到工程师令狐小哥的频道。都说现在的时代是AI程序员的时代。AI程序员标志着程序员的生产力工具已经由原来的搜索式…

JavaSE之String类

文章目录 一、String类常用的构造方法二、常见的四种String对象的比较1.使用比较2.使用equals()方法比较3.使用compareTo()方法比较4.使用compareToIgnoreCase()方法比较 三、字符串的查找四、字符串的转化1.数字和字符串间的转化2.大小写转化3.字符串和数组间的转化 五、字符串…

grafana 配置prometheus

安装prometheus 【linux】麒麟v10安装prometheus监控&#xff08;ARM架构&#xff09;-CSDN博客 登录grafana 访问地址&#xff1a;http://ip:port/login 可以进行 Grafana 相关设置&#xff08;默认账号密码均为 admin&#xff09;。 输入账户密码 添加 Prometheus 数据源…

Codeforces Round 979 (Div. 2)

A. A Gift From Orangutan 题意&#xff1a; 思路&#xff1a; 贪心 模拟 重新排列的数组 -> 最大的元素放第一个位置 &#xff0c;最小的元素放第二个位置 #include<bits/stdc.h> using namespace std; #define lowbit(x) ( x & -x )#define int long long ty…

人类末日?Hinton预言AI恐将夺取地球控制权!

图片来源&#xff1a;Youtube Z Highlights&#xff1a; AI会变得比人类更聪明。我们必须担心它们会想从我们手中夺取控制权&#xff0c;这是我们应该认真思考的问题。 使用AI制造自动化致命武器的风险并不取决于AI是否比我们聪明。这与AI本身可能失控并试图接管的风险是完全…

[论文笔记]HERMES 3 TECHNICAL REPORT

引言 今天带来论文HERMES 3 TECHNICAL REPORT&#xff0c;这篇论文提出了一个强大的工具调用模型&#xff0c;包含了训练方案介绍。同时提出了一个函数调用标准。 为了简单&#xff0c;下文中以翻译的口吻记录&#xff0c;比如替换"作者"为"我们"。 聊天模…

嵌套div导致子区域margin失效问题解决

嵌套div导致子区域margin失效问题解决 现象原因解决方法 现象 <div class"prev"></div> <div class"parent"><div class"child"></div><div class"child"></div> </div> <div cl…

HCIP到底需要考哪几门?821和831都要考吗?

相对于华为认证中的HCIE&#xff0c;HCIP难度较低比较容易获得。 对于许多准备考HCIP认证的朋友来说&#xff0c;了解考试要求和内容是成功的关键第一步。 经常问的问题上次刚梳理了一波价格&#xff0c;还没看的看这里→《HCIP考证多少钱&#xff1f;HCIP认证深度解析》 今天再…