【每日算法/刷穿 LeetCode】24. 两两交换链表中的节点(中等)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【每日算法/刷穿 LeetCode】24. 两两交换链表中的节点(中等),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2229字,纯文字阅读大概需要4分钟。
内容图文
点击 这里 可以查看更多算法面试相关内容~
题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
- 链表中节点的数目在范围
[0, 100]
内 0 <= Node.val <= 100
递归解法(哨兵技巧)
哨兵技巧我们之前在前面的多道链表题讲过,让三叶来帮你回忆一下:
做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。
链表和树的题目天然适合使用递归来做。
我们可以设计一个递归函数,接受一个 ListNode
节点 root 作为参数,函数的作用是将 root 后面的两个节点进行交换,交换完成后再将下一个节点传入 …
交换的前提条件:节点 root 后面至少有两个节点。同时别忘了应用我们的「哨兵技巧」:
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
recursive(dummy);
return dummy.next;
}
void recursive(ListNode root) {
if (root.next != null && root.next.next != null) {
ListNode a = root.next, b = a.next;
root.next = b;
a.next = b.next;
b.next = a;
recursive(a);
}
}
}
-
时间复杂度:会将每个节点处理一遍。复杂度为 O(n)
-
空间复杂度:O(1)
迭代解法(哨兵技巧)
所有的递归都能转化为迭代:
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
for (ListNode cur = dummy; cur.next != null && cur.next.next != null;) {
ListNode a = cur.next, b = a.next;
cur.next = b;
a.next = b.next;
b.next = a;
cur = a;
}
return dummy.next;
}
}
-
时间复杂度:会将每个节点处理一遍。复杂度为 O(n)
-
空间复杂度:O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.24
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 24/1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:Github 地址 & Gitee 地址。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
#算法与数据结构
#LeetCode题解
#算法面试
内容总结
以上是互联网集市为您收集整理的【每日算法/刷穿 LeetCode】24. 两两交换链表中的节点(中等)全部内容,希望文章能够帮你解决【每日算法/刷穿 LeetCode】24. 两两交换链表中的节点(中等)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。