关键词:
大家好呀,我是蛋蛋。
今天开搞交换链表,和反转链表一样,也是必考的“老熟人”。
话不多说,直接开工。
LeetCode 24:交换链表
题意
两两交换链表相邻节点的值,返回交换后的链表。
示例
输入:head = [1, 2, 3, 4]
输出: [2, 1, 4, 3]
提示
0 <= 链表节点数 <= 100
0 <= Node.val <= 100
题目解析
水题,难度中等。
这道题要求不能只是单纯的改变节点内部得值,需要进行实际的节点交换。
和反转链表一样,这类链表题思维上没有难度,就是每次从链表上截取两个节点进行交换。
主要是考察代码实现能力。
这道题我用带虚拟头节点的单链表实现。
虚拟头节点(其实我以前都叫头节点,后来有臭宝和我说容易看混,我就叫虚拟头节点),可能很多人叫做哨兵节点,放在第一个元素的节点之前,数据域一般没意义。
图解
先建立一个带虚拟头节点的单链表。
PS:此处代码为 Python(”代码实现“小节处有 Java 代码,下同)。
# 链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 创建虚拟节点
dummyHead = ListNode(-1)
因为每次要截取两个节点进行交换,初始建立 3 个指针 pre,p 和 q。
其中 pre 指向虚拟头节点,p 指向链表首节点,q 指向链表的第 2 个节点。
pre = dummyHead
p = head
q = p.next
节点两两交换主要分为 3 步。
第 1 步:pre 的后继指针 next 指向 q,即 pre.next = q。
第 2 步:p 的后继指针 next 指向 q 的后继节点,即 p.next = q.next。
第 3 步:那就剩了 q 的后继指针 next 指向 p,即 q.next = p。
所以第一次交换完,链表变成了:
pre.next = q
p.next = q.next
q.next = p
接下来就是 pre、p 和 q 指针同时右移。
pre = p
p = p.next
q = p.next
继续重复上述 3 步操作。
本方法遍历一遍链表,时间复杂度为 O(n),空间复杂度为 O(1)。
代码实现
Python 代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 空链表或者只有一个节点,直接返回
if not head or head.next == None:
return head
# 创建虚拟节点
dummyHead = ListNode(-1)
# 初始化pre、p 节点
pre = dummyHead
p = head
# 必须是节点数是偶数个的时候才能交换
# 如果最后只剩下一个节点,即链表是奇数个节点,最后一个不用反转
# 比如 head = [1,2, 3, 4, 5],输出 [2, 1, 4, 3, 5]
while p and p.next:
# 初始化 q 节点
q = p.next
# 交换节点 3 步走
pre.next = q
p.next = q.next
q.next = p
# 指针右移
pre = p
p = p.next
# 返回链表
return dummyHead.next
Java 代码实现
// 虚拟头结点
class Solution
public ListNode swapPairs(ListNode head)
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode prev = dummyNode;
while (prev.next != null && prev.next.next != null)
ListNode temp = head.next.next; // 缓存 next
prev.next = head.next; // 将 prev 的 next 改为 head 的 next
head.next.next = head; // 将 head.next(prev.next) 的next,指向 head
head.next = temp; // 将head 的 next 接上缓存的temp
prev = head; // 步进1位
head = head.next; // 步进1位
return dummyNode.next;
图解交换链表到这就结束啦。
按照我的图解在纸上画一下加深印象,步骤不要出错。
在这我还是要叨叨叨,这类题思维上么的难度,考代码实现!臭宝们一定要多多练习,代码熟记,肌肉记忆。
当然辣,你们的一键三连么么哒也给我肌肉记忆起来呀~
我是帅蛋,我们下次见!
图解leetcode206:反转吧,链表!(代码片段)
...#xff0c;反转链表都属于必考项。话不多说,直接开工。LeetCode206:反转链表题意给出单链表的头节点head,反转链表,返回反转后的链表。示例输入 查看详情
图解leetcode206:反转吧,链表!(代码片段)
...#xff0c;反转链表都属于必考项。话不多说,直接开工。LeetCode206:反转链表题意给出单链表的头节点head,反转链表,返回反转后的链表。示例输入 查看详情
「leetcode」24.两两交换链表中的节点(代码片段)
两两交换链表中的节点给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]示... 查看详情
「leetcode」24.两两交换链表中的节点(代码片段)
两两交换链表中的节点给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]示... 查看详情
leetcode24两两交换链表中的节点(代码片段)
https://leetcode-cn.com/problems/swap-nodes-in-pairs/、解决方案classSolutionpublicListNodeswapPairs(ListNodehead)if(head!=null&&head.next!=null)ListNodenode=head.next;head.next=swapPairs(head.next.next);node.next=head;returnnode;returnhead; 查看详情
leetcode两两交换链表中的节点(24)(代码片段)
文章目录题目描述方法一:递归思路与算法复杂度分析方法二:迭代思路与算法复杂度分析题目描述给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而... 查看详情
算法leetcode|24.两两交换链表中的节点(rust重拳出击)(代码片段)
文章目录24.两两交换链表中的节点:样例1:样例2:样例3:提示:分析:题解:rustgoc++cpythonjava24.两两交换链表中的节点:给你一个链表,两两交换其中相邻的节点,并返回交换后链表... 查看详情
算法leetcode|24.两两交换链表中的节点(rust重拳出击)(代码片段)
文章目录24.两两交换链表中的节点:样例1:样例2:样例3:提示:分析:题解:rustgoc++cpythonjava24.两两交换链表中的节点:给你一个链表,两两交换其中相邻的节点,并返回交换后链表... 查看详情
leetcode24.两两交换链表中的节点c++/java详细题解(代码片段)
目录1、题目2、思路3、c++代码4、java代码1、题目给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。示例1:输入:head&... 查看详情
leetcode24.两两交换链表中的节点(代码片段)
24.两两交换链表中的节点力扣题目跳转链接具体解题思路和答案可以参考:代码随想录:24.两两交换链表中的节点自我错误思考过程记录:✘错误代码://思路:classSolutionpublic:ListNode*swapPairs(ListNode*head)ListNode*dummyHead=ListNode... 查看详情
☆打卡算法☆leetcode24两两交换链表中的节点算法解析(代码片段)
推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记... 查看详情
24链表-两两交换链表中的结点(代码片段)
题目链接:24.两两交换链表中的节点-力扣(LeetCode) 思路画图模拟即可,分为三步,如图。一轮结束后cur向后移动两位。代码:/***Definitionforsingly-linkedlist.*structListNode*intval;*ListNode*next;*ListNode():val(0) 查看详情
☆打卡算法☆leetcode24两两交换链表中的节点算法解析(代码片段)
...回交换后的链表。”题目链接:来源:力扣(LeetCode)链接:24.两两交换链表中的节点-力扣(LeetCode)(leetcode-cn.com)2、题目描述给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。... 查看详情
leetcode-24-两两交换链表中等的节点-java(代码片段)
前言对单链表还不熟悉的朋友,可以参考这篇文章顺序表和链表-单向链表部分题目这个题目不好讲,我直接将代码和解析图给你们,需要你们自己多琢磨。当然一些重要代码部分我会注释一下! 递归解法classSolu... 查看详情
24.两两交换链表中的节点(代码片段)
算法记录LeetCode题目: 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。思路算法记录说明一、题目二、分析总结说明一、题目 你不能只是单纯的改变节点内部的值,而是需要实际的进行... 查看详情
交换吧,链表!
...;也是必考的“老熟人”。话不多说,直接开工。 LeetCode24:交换链表题意两两交换链表相邻节点的值,返回交换后的链表。示例输入:head= [1,2,3,4]输出: [2,1,4,3]提示0< 查看详情
图解leetcode141:链表,你有环嘛?(代码片段)
...在思维上稍微复杂一点儿,但是不慌,有我在。LeetCode141:环形链表题意给定一个链表,判断链表中是否有环。示例使用整数pos表示链表尾连接到链表中的位置(索引从0开始)。输入:head=[3,2,0,-4] 查看详情
图解leetcode141:链表,你有环嘛?(代码片段)
...在思维上稍微复杂一点儿,但是不慌,有我在。LeetCode141:环形链表题意给定一个链表,判断链表中是否有环。示例使用整数pos表示链表尾连接到链表中的位置(索引从0开始)。输入:head=[3,2,0,-4] 查看详情