zl程序教程

您现在的位置是:首页 >  后端

当前栏目

两两交换链表中的节点

链表节点 交换
2023-09-27 14:23:02 时间

problem

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

例如:
在这里插入图片描述

利用stack

我们利用一个 stack,然后不断迭代链表,每次取出两个节点放入 stack 中,再从 stack 中拿出两个节点。
借助 stack 后进先出的特点,放进去的时候是 1,2 。拿出来的时候就是 2,1 两个节点了。
再把这两个节点串联起来,重复这个逻辑遍历完整个链表,就可以做到两两反转的效果了。
虽然用到了 stack,但因为只存了两个元素,所以空间复杂度还是 O(1),时间复杂度是 O(n)。

在这里插入图片描述