【打卡算法】 24、两两交换链表中的节点 算法解析

恬静的小魔龙 发表于 2022/07/28 22:11:54 2022/07/28
【摘要】 推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875 大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“将给定链表中相邻的节点交换,返回交换后的链表。”

题目链接:

来源:力扣(LeetCode)

链接:24. 两两交换链表中的节点 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

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

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MeaiTuWm-1658998642013)(https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/1057fd97c9aa4c499f879d8b2a4a83ad~tplv-k3u1fbpfcp-watermark.image?)]

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

  
 
  • 1
  • 2
  • 3
示例 2:
输入: head = [1]
输出: [1]

  
 
  • 1
  • 2
  • 3

二、解题

1、思路分析

这个题可以采用递归的方式实现链表中相邻节点的交换。

递归的终止条件是链表中没有节点,或者链表中只有一个节点,这个时候无法进行交换。

那么接下来就是交换了,比如,链表中有两个节点,在交换节点后,原链表的头结点就变成新链表的第二个节点,原链表的第二个节点变成新链表的头结点。

其余节点递归地实现,递归地两两交换后,更新节点之间的指针关系,即可完成整个链表的交换。

2、代码实现

代码参考:

public class Solution {
    public ListNode SwapPairs(ListNode head) {
            //递归结束判断
            if (head?.next == null)
                return head;
            //替换
            var val = head.next.val;
            head.next.val = head.val;
            head.val = val;
            //递归
            SwapPairs(head.next.next);
            return head;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3FHSOyuF-1658998642015)(https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/502317d6ac4242b3bd03a26740c1f464~tplv-k3u1fbpfcp-watermark.image?)]

3、时间复杂度

时间复杂度 : O(n)

其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。

空间复杂度: O(n)

其中 n 是链表的节点数量。空间复杂度主要取决于递归调用的栈空间。

三、总结

继续引用那句话,递归就像学霸学习,看似什么都没做,其实都做完了。

文章来源: itmonon.blog.csdn.net,作者:恬静的小魔龙,版权归原作者所有,如需转载,请联系作者。

原文链接:itmonon.blog.csdn.net/article/details/126038980

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。