【优选算法专栏】专题九:链表--------两两交换链表中的节点

简介: 【优选算法专栏】专题九:链表--------两两交换链表中的节点


题目来源

本题来源为:

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

题目解析

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

算法原理

本题的算法还是模拟

首先画一下图:

这里我们会发现,要是两两进行交换,会影响四个节点的位置,因此我们要定义四个变量:

画图观察,交换后每个节点的指向就十分明确。

那么什么时候循环结束呢?

分两种情况:

  1. 节点个数为偶数时:

    cur为空时结束循环
  2. 节点个数为奇数时:

    next为空时,循环结束

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        //当传入的链表为空或者一个节点时,直接返回
        if(head==nullptr||head->next==nullptr)
        return head;
        //创建虚拟头节点
        ListNode* newhead=new ListNode(0);
        newhead->next=head;
        //定义变量
        ListNode*prev=newhead,*cur=prev->next,*next=cur->next,*nnext=next->next;
        while(cur&&next)
        {
            //交换节点:
            prev->next=next;
            next->next=cur;
            cur->next=nnext;
            //修改节点:
            prev=cur;
            cur=nnext;
            //注意非法访问
            if(cur)
            next=cur->next;
            if(next)
            nnext=next->next;
        }
        cur=newhead->next;
        delete newhead;
        return cur;
    }
};
相关文章
|
4天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
12 0
|
4天前
|
网络协议 算法 数据库
【专栏】IS-IS协议是内部网关协议,常用于大型网络路由器间的路由信息交换,基于OSI的CLNP标准和Dijkstra算法
【4月更文挑战第28天】IS-IS协议是内部网关协议,常用于大型网络路由器间的路由信息交换,基于OSI的CLNP标准和Dijkstra算法。其特点是分层设计、快速收敛、高效资源利用和强故障恢复能力。在现代网络中,IS-IS广泛应用于服务提供商、企业网络及与其他协议的融合,是构建稳定、高效网络的关键。了解和应用IS-IS能提升网络系统的可靠性和效率。
|
4天前
|
存储 算法
双链表——“数据结构与算法”
双链表——“数据结构与算法”
|
4天前
|
算法
算法系列--链表刷题(二)(下)
算法系列--链表刷题(二)(下)
18 0
|
4天前
|
算法
算法系列--链表刷题(二)(上)
算法系列--链表刷题(二)
19 0
|
4天前
|
算法
算法系列--递归(一)--与链表有关(下)
算法系列--递归(一)--与链表有关(下)
21 0
|
4天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
1天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
19 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
|
2天前
|
算法
MATLAB|【免费】融合正余弦和柯西变异的麻雀优化算法SCSSA-CNN-BiLSTM双向长短期记忆网络预测模型
这段内容介绍了一个使用改进的麻雀搜索算法优化CNN-BiLSTM模型进行多输入单输出预测的程序。程序通过融合正余弦和柯西变异提升算法性能,主要优化学习率、正则化参数及BiLSTM的隐层神经元数量。它利用一段简单的风速数据进行演示,对比了改进算法与粒子群、灰狼算法的优化效果。代码包括数据导入、预处理和模型构建部分,并展示了优化前后的效果。建议使用高版本MATLAB运行。
|
4天前
|
算法 计算机视觉
基于高斯混合模型的视频背景提取和人员跟踪算法matlab仿真
该内容是关于使用MATLAB2013B实现基于高斯混合模型(GMM)的视频背景提取和人员跟踪算法。算法通过GMM建立背景模型,新帧与模型比较,提取前景并进行人员跟踪。文章附有程序代码示例,展示从读取视频到结果显示的流程。最后,结果保存在Result.mat文件中。