想要精通算法和SQL的成长之路 - 两两交换链表中的节点

news/2024/10/31 3:22:36/

想要精通算法和SQL的成长之路 - 两两交换链表中的节点

  • 前言
  • 一. 两两交换链表中的节点

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 两两交换链表中的节点

原题链接
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

在这里插入图片描述

写这道题目之前,可以先看下 反转链表。这题只不过是它的一个进阶版。

思路如下(借用了代码随想录的思路图):
在这里插入图片描述
按照红色的箭头进行指针变更,不过有几个值得注意的点给大家说下:

  1. 我们需要用一个虚拟指针 h。并使得 h.next = head;。这样做的目的:使得原链表的所有节点按照统一的方式进行操作替换。否则头结点就可能需要单独处理。
  2. 在修改指针的时候,我们往往需要使用几个临时变量去存储指针对象。这样做的目的:因为一旦值被替换了,原值就不复存在了,那就无法进行值/引用的交换了。
  3. 这类反转的题目,一定要手动画图,整理好顺序,写代码就方便容易理解了。

例如以下代码:

int a = 1,b = 2;
a=b;
b=a;

上面的值交换的写法就是错误的。最终a和b的值都是2。正确的应该是:

int a = 1, b = 2;
int tmp = b;
b = a;
a = tmp;

其实这是个很简单的道理,但是往往在链表的指针替换时候,很多人却不知道为什么这样做(有可能都是nextpre的操作,整蒙圈了)。

最终代码如下:

public ListNode swapPairs(ListNode head) {// 构建一个虚拟节点ListNode h = new ListNode(0);h.next = head;ListNode cur = h;while (cur.next != null && cur.next.next != null) {// 把这两个值缓存起来ListNode tmp1 = cur.next;ListNode tmp2 = cur.next.next.next;// 第一步,相邻节点的头结点变更cur.next = cur.next.next;// 第二步:相邻节点之间的引用互换cur.next.next = tmp1;// 第三部,相邻节点的尾结点变更cur.next.next.next = tmp2;// 当前节点往后移动两位,进入下一层循环cur = cur.next.next;}// 返回链表return h.next;
}

http://www.ppmy.cn/news/271493.html

相关文章

Kernel: module: Invalid module format

https://www.man7.org/linux/man-pages/man3/memcmp.3.html 这个错误的报出点是kmod这个开源模块里的insmod.c: static const char *mod_strerror(int err) {switch (err) {case ENOEXEC:return "Invalid module format";出现ENOEXEC的地方是,说这个size 小于EI_…

Spring 依赖注入

一、 通过<property>和<constructor-arg>标签赋值注入&#xff0c;本质是set方法&#xff0c;详见Spring bean四种的创建方式以及作用域的设置 二、 通过命名空间p标签实现属性值&#xff0c;本质还是set方法&#xff08;古老&#xff0c;少见&#xff09; 1、xml中…

强化学习开篇-那些问123

1、强化学习的基本结构是什么&#xff1f; 智能体和环境。智能体基于当前状态&#xff0c;采取动作&#xff0c;环境给出反馈也就是奖励&#xff0c;再去更新当前的状态。 2、强化学习相对于监督学习为什么训练过程会更加困难&#xff1f; 监督学习的样本一般是相互独立的&am…

接口测试框架实战 | 通用 API 封装实战

接口测试仅仅掌握 Requests 或者其他一些功能强大的库的用法&#xff0c;是远远不够的&#xff0c;还需要具备能根据公司的业务流程以及需求去定制化一个接口自动化测试框架的能力。所以&#xff0c;接下来&#xff0c;我们主要介绍下接口测试用例分析以及通用的流程封装是如何…

中国传统色的雅称——你可知?

梅染、荼白、落栗、薄柿、酡颜、踯躅、曙色、缁色、鸦青、胭脂、若草、缟、缃色、竹青、苏芳、缥色、天水碧、月白、远山如黛、青梅煮酒、桥下春波。 这些颜色的名字&#xff0c;是不是看着美极了。 中国传统颜色的雅称&#xff0c;你都知道吗&#xff1f; 梅染 梅染顾名思义&a…

分享一组超喜欢的粉色樱花高清壁纸~

向往漫天的樱花&#xff1f;想要一款治愈系的桌面大图&#xff1f;推荐粉色樱花高清壁纸给大家使用&#xff0c;壁纸粉色设计&#xff0c;温婉柔和超治愈&#xff0c;为您带来好心情

多套头像/壁纸/背景图资源微信小程序源码 粉色UI 带流量主

云开发版粉色UI微信小程序源码&#xff0c;背景图、头像、壁纸小程序源码&#xff0c;带流量主功能。 云开发小程序源码无需服务器和域名即可搭建小程序另外还带有流量主功能噢&#xff01;微信平台注册小程序就可以了。 这套粉色UI非常的好看&#xff0c;里面保护有背景图、…

粉色的牡丹花Mac动态壁纸

丹花有着花中之王的美名,其雍容华贵的外形十分让人喜爱。 粉色的牡丹花动态壁纸