题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
难度:Middle
前置知识
- 链表
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
设置一个 dummy 节点简化操作,dummy next 指向 head。
- 初始化 first 为第一个节点
- 初始化 second 为第二个节点
- 初始化 current 为 dummy
- first.next = second.next
- second.next = first
- current.next = second
- current 移动两格
- 重复
(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)
关键点解析
- 链表这种数据结构的特点和使用
-
dummyHead 简化操作
代码
- 语言支持:JS,Python3
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
const dummy = new ListNode(0);
dummy.next = head;
let current = dummy;
while (current.next != null && current.next.next != null) {
// 初始化双指针
const first = current.next;
const second = current.next.next;
// 更新双指针和 current 指针
first.next = second.next;
second.next = first;
current.next = second;
// 更新指针
current = current.next.next;
}
return dummy.next;
};
Python3 Code:
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
"""
用递归实现链表相邻互换:
第一个节点的 next 是第三、第四个节点交换的结果,第二个节点的 next 是第一个节点;
第三个节点的 next 是第五、第六个节点交换的结果,第四个节点的 next 是第三个节点;
以此类推
:param ListNode head
:return ListNode
"""
# 如果为 None 或 next 为 None,则直接返回
if not head or not head.next:
return head
_next = head.next
head.next = self.swapPairs(_next.next)
_next.next = head
return _next
复杂度分析
– 时间复杂度:$O(N)$
– 空间复杂度:$O(1)$
– 原题leetcode链接:24.swapNodesInPairs
更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com