前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >反转还不行,要两两交换!

反转还不行,要两两交换!

作者头像
代码随想录
发布2021-06-17 15:43:21
4380
发布2021-06-17 15:43:21
举报
文章被收录于专栏:代码随想录

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

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

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

思路

这道题目正常模拟就可以了。

建议使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。

对虚拟头结点的操作,还不熟悉的话,可以看这篇链表:听说用虚拟头节点会方便很多?

接下来就是交换相邻两个元素了,此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序

初始时,cur指向虚拟头结点,然后进行如下三步:

操作之后,链表如下:

看这个可能就更直观一些了:

对应的C++代码实现如下:(注释中详细和如上图中的三步做对应)

代码语言:javascript
复制
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head,这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位,准备下一轮交换
        }
        return dummyHead->next;
    }
};
  • 时间复杂度:
O(n)
  • 空间复杂度:
O(1)

拓展

这里还是说一下,大家不必太在意力扣上执行用时,打败多少多少用户,这个统计不准确的。

做题的时候自己能分析出来时间复杂度就可以了,至于力扣上执行用时,大概看一下就行。

上面的代码我第一次提交执行用时8ms,打败6.5%的用户,差点吓到我了。

心想应该没有更好的方法了吧,也就O(n)的时间复杂度,重复提交几次,这样了:

力扣上的统计如果两份代码是 100ms 和 300ms的耗时,其实是需要注意的。

如果一个是 4ms 一个是 12ms,看上去好像是一个打败了80%,一个打败了20%,其实是没有差别的。只不过是力扣统计的误差而已。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-05-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 代码随想录 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 思路
  • 拓展
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档