【题目】链表相关算法题

文章目录

  • 一. 合并两个有序链表
    • 题目解析
    • 算法原理
    • 代码编写
  • 二. 相交链表问题
    • 题目解析
    • 算法原理
    • 代码编写
  • 三. 环形链表问题
    • 1. 判断是否有环
    • 2. 计算环的长度
    • 3. 找到环的入口点
  • 四. 反转链表
    • 方法一：边迭代、边逆置
    • 方法二：头插
  • 五. 判断链表是否回文
    • 题目解析
    • 算法原理
    • 代码编写
  • 六、删除排序链表中的重复元素问题
    • 1. 删除排序链表中的重复元素I
    • 2. 删除排序链表中的重复元素II
  • 七. 随机链表的复制
    • 题目解析
    • 算法原理
    • 代码编写

一. 合并两个有序链表

题目解析

在这里插入图片描述

算法原理

同时遍历两个链表，取 val 小的那个节点尾插到新链表中

在这里插入图片描述

代码编写

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 1、预处理(创建哨兵位头节点)
        ListNode* head, *tail;
        head = tail = new ListNode();
        // 2、遍历并合并两个两个链表
        while(list1 != nullptr && list2 != nullptr)
        {
            if(list1->val < list2->val) 
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        // 3、处理未遍历完的那个链表
        if(list1 != nullptr) tail->next = list1;
        else tail->next = list2;
        // 4、返回最终结果
        ListNode* ans = head->next;
        delete head;
        return ans;
    }
};

二. 相交链表问题

题目解析

在这里插入图片描述

算法原理

在这里插入图片描述

代码编写

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 1、判断两个链表是否相交 && 计算两个链表的长度
        int lenA = 1, lenB = 1; //链表长度
        ListNode *ltA = headA, *ltB = headB; //链表最后一个节点
        while(ltA && ltA->next) ltA = ltA->next, ++lenA; //寻找A最后一个节点 和 统计链表长度
        while(ltB && ltB->next) ltB = ltB->next, ++lenB; //寻找B最后一个节点 和 统计链表长度
        if(ltA != ltB) return nullptr; //判断是否相交
        // 2、寻找初始相交节点
        int gap = abs(lenA - lenB); //链表长度差值
        ListNode *longList = headA, *shortList = headB; //创建长、短链表指针
        if(lenA < lenB) std::swap(longList, shortList);//确认长、短链表指针
        while(gap--) longList = longList->next; //长链表先走 gap 步
        while(longList != shortList) //两个链表同步走
        {
            longList = longList->next;
            shortList = shortList->next;
        }
        // 3、返回值
        return longList; 
    }
};
/*
- 时间复杂度：O(m+n)
- 空间复杂度：O(1)
*/

三. 环形链表问题

1. 判断是否有环

解题思路
在这里插入图片描述

代码编写

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;

bool hasCycle(struct ListNode *head) 
{
    //空链接情况的处理
    if(!head)
    {
        return false;
    }
    ListNode* fast=head;
    ListNode* slow=head;
    //fast一次走两步，为了防止空指针的访问要两个条件的判断
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

2. 计算环的长度

算法原理
在这里插入图片描述

3. 找到环的入口点

算法原理
在这里插入图片描述

代码编写

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //先记录fast和slow相遇时的节点
 //在定义一个节点从头开始
 //二者每次走一步
 //最后相遇时的节点就是入环节点

typedef struct ListNode ListNode;

struct ListNode *detectCycle(struct ListNode *head) 
{    
    ListNode* slow=head;
    ListNode* fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            ListNode* meet=slow;
            while(1)
            {
                if(head==meet)
                {
                    return head;
                }
                head=head->next;
                meet=meet->next;
            }
        }
    }
    return NULL;
}

四. 反转链表

在这里插入图片描述

方法一：边迭代、边逆置

算法原理
在这里插入图片描述

代码编写

// 方法一：边迭代、边逆置 
class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(!head) return nullptr;
        // 1、初始化
        ListNode* n1 = nullptr;
        ListNode* n2 = head;
        ListNode* n3 = head->next;
        // 2、逆置
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3) n3 = n3->next;
        }
        // 3、返回值
        return n1;
    }
};

方法二：头插

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        // 1、初始化
        ListNode* cur = head, *newHead = nullptr;
        // 2、头插
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        // 3、返回值
        return newHead;
    }
};

五. 判断链表是否回文

题目解析

算法原理

在这里插入图片描述

代码编写

/**
 * 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 
{
private:
    ListNode* ReverseList(ListNode* head)
    {
        if(!head) return nullptr;
        ListNode* n1 = nullptr, *n2 = head, *n3 = head->next;
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3) n3 = n3->next;
        }
        return n1;
    }

public:
    bool isPalindrome(ListNode* head) 
    {
        // 1、找到中间节点
        ListNode* fast, *slow;
        fast = slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 2、逆置后半段链表
        ListNode* half = ReverseList(slow);
        // 3、比较前后部分链表
        while(head && half)
        {
            if(head->val != half->val) return false;
            head = head->next;
            half = half->next;
        }
        // 4、返回值
        return true;
    }
};

六、删除排序链表中的重复元素问题

1. 删除排序链表中的重复元素I

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

/**
 * 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* deleteDuplicates(ListNode* head) 
    {
        // 0、特殊情况处理（保证链表至少有两个节点才做处理）
        if(head == nullptr || head->next == nullptr) return head;
        // 1、初始化
        ListNode* newHead, *tail;  
        newHead = tail = head;//新链表第一个节点为 head
        head = head->next;    //旧链表从第二个节点开始遍历 
        tail->next = nullptr; //设置新链表中第一个节点的 next 为空  
        // 2、删除重复元素
        while(head)
        {
            ListNode* cur = head;
            head = head->next;
            if(cur->val != tail->val)
            {
                tail->next = cur;
                tail = cur;
                tail->next = nullptr;
            }
        }
        // 3、返回值
        return newHead;
    }
};

2. 删除排序链表中的重复元素II

在这里插入图片描述

算法原理
在这里插入图片描述
代码编写

/**
 * 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* deleteDuplicates(ListNode* head) 
    {
        // 0、特殊情况处理（保证链表至少有两个节点才做处理）
        if(head == nullptr || head->next == nullptr) return head;
        // 1、初始化
        ListNode* newHead, *tail;  
        newHead = tail = head;//新链表第一个节点为 head
        head = head->next;    //旧链表从第二个节点开始遍历 
        tail->next = nullptr; //设置新链表中第一个节点的 next 为空  
        // 2、删除重复元素
        while(head)
        {
            ListNode* cur = head;
            head = head->next;
            if(cur->val != tail->val)
            {
                tail->next = cur;
                tail = cur;
                tail->next = nullptr;
            }
        }
        // 3、返回值
        return newHead;
    }
};

七. 随机链表的复制

题目解析

在这里插入图片描述

算法原理

在这里插入图片描述

代码编写

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        // 1、拷贝节点到原节点的后面
        Node* cur = head;
        while(cur)
        {
            // 初始化
            Node* copy = new Node(cur->val);
            Node* next = cur->next;
            // 链接
            cur->next = copy;
            copy->next = next;
            // 更新cur
            cur = next;
        }
        // 2、处理拷贝节点的 random 指针
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
            if(cur->random) 
                copy->random = cur->random->next;
            // 继续迭代原链表的下一个节点
            cur = cur->next->next;
        }
        // 3、拆解链表
        Node* newHead, *tail; //创造一个哨兵位头节点
        newHead = tail = new Node(0);
        cur = head;
        while(cur)
        {
            // 初始化
            Node* copy = cur->next;
            Node* next = cur->next->next;
            // 尾插拷贝节点到新链表中
            tail->next = copy;
            tail = copy;
            tail->next = nullptr;
            // 处理原链表节点
            cur->next = next;
            cur = next;
        }
        // 4、返回值
        return newHead->next;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/209873.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LinkedList详解

LinkedList详解

LinkedList详解 LinkedList是List接口的一个主要的实现类之一&#xff0c;基于链表的实现。以java8为例来了解一下LinkedList的源码实现 继承关系 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>,…
阅读更多...
进制转化总结

进制转化总结

来源&#xff0c;做个笔记&#xff0c;讲的还蛮清楚通信原理-2.5 数据封装与传输05_哔哩哔哩_bilibili ip地址范围
阅读更多...
6 新建工程——寄存器

6 新建工程——寄存器

文章目录 6.1 本地新建工程文件夹6.2 新建工程6.2.1 选择CPU型号6.2.2 在线添加库文件6.2.3 添加文件6.2.4 复制存储器分配文件6.2.5 配置选项卡6.2.5.1 Linker6.2.5.2 Target6.2.5.3 Output 选项卡6.2.5.4 Listing 选项卡6.2.6 下载器配置 版本说明&#xff1a;MDK5.24 6.1 本…
阅读更多...
许战海战略文库|重回大众视野的健力宝如何重生

许战海战略文库|重回大众视野的健力宝如何重生

摘要&#xff1a;销售额连续7年没有增长;产业主品牌定位不清晰;产品不协同缺少产品战略;子品牌无法形成合力新产品共性不足;过度差异化缺少渠道战略;被渠道能力更强的品牌挤压。火遍世界的“东方魔水”从第一品牌到被人遗忘&#xff0c;健力宝该如何重生? 健力宝诞生于1984年&…
阅读更多...
css 三栏布局的实现

css 三栏布局的实现

三栏布局在前端页面设计中是一个常见的布局方式&#xff0c;通常包含左侧、中间和右侧三个部分。这种布局方式在多种场景中都很受欢迎&#xff0c;例如博客、新闻网站和企业官网。本文将详细介绍三栏布局的实现方法&#xff0c;包括用法、代码、深入理解&#xff0c;以及配合高…
阅读更多...
Python编程基础：输入/输出函数、注释与缩进

Python编程基础：输入/输出函数、注释与缩进

Python是一种简单易学的编程语言&#xff0c;广泛应用于Web开发、数据分析、人工智能等领域。无论您是初学者还是有一定编程经验的人士&#xff0c;都可以从Python的基础知识开始建立自己的编程技能。 目录 理论Python语言的发展程序设计语言的分类静态语言与脚本语言的区别 代…
阅读更多...
解决element ui tree组件不产生横向滚动条

解决element ui tree组件不产生横向滚动条

结果是这样的 需要在tree的外层&#xff0c;包一个父组件 <div class"tree"><el-tree :data"treeData" show-checkbox default-expand-all></el-tree></div> 在css里面这样写,样式穿透按自己使用的css编译器以及框架要求就好 &l…
阅读更多...
笔记：Pika Labs 3D 动画生成工具

笔记：Pika Labs 3D 动画生成工具

Pika Labs 一款3D 动画生成工具 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/134657306 目 录 1. 简介2. 准备2.1 安装 discord2.2 加入 Discord 频道 3. Pika 使用指南2.1 快速开始2.2 从图像到视频2.3 Pika Bot按钮2.4 提示&#xff08;Prompt&a…
阅读更多...
WPF Live Charts2 自学笔记

WPF Live Charts2 自学笔记

文章目录 前言实现效果微软平台的历史问题 WPF 项目搭建Nuget添加额外框架添加项目初始化livecharts配置其它LiveCharts2 案例简单案例Demo示例ViewViewModel GPU渲染 Github地址仓库 前言 LiveChart 是C# 上面很受欢迎的统计图 UI控件。最近在学WPFhalcon开发&#xff0c;想想…
阅读更多...
肖sir__mysql之单表练习题2__(2)

肖sir__mysql之单表练习题2__(2)

mysql之单表练习题 一.建表语句 create table grade(class int(4),chinese int(8),english int(4),math int(8),name varchar(20),age int(8),sid int(4)primary key auto_increment) DEFAULT charsetutf8; insert into grade(class,chinese,english,math,name,age)values(1833…
阅读更多...
在Android上搭建一个NDK项目

在Android上搭建一个NDK项目

首先New Project&#xff0c;选择Native C&#xff0c;点击Next。 填入项目名称和包名&#xff0c;点击Next。 这里我们选择Cmake默认的C版本。 创建好的项目目录&#xff0c;里面比我们正常的Android项目多了一个cpp目录 打开MainActivity。里面定义了一个jni方法stringFromJN…
阅读更多...
LLM；超越记忆《第 2 部分 》

LLM；超越记忆《第 2 部分 》

一、说明 在这篇博客中&#xff0c;我深入研究了将大型语言模型&#xff08;LLM&#xff09;提升到基本记忆之上的数学框架。我们探索了动态上下文学习、连续空间插值及其生成能力&#xff0c;揭示了 LLM 如何理解、适应和创新超越传统机器学习模型。 LLM代表了人工智能的重大飞…
阅读更多...
如何使用 NFTScan NFT API 在 Starknet 网络上开发 Web3 应用

如何使用 NFTScan NFT API 在 Starknet 网络上开发 Web3 应用

Starknet 是由以色列软件公司 StarkWare 开发的免许可的第 2 层网络。Starknet 作为以太坊上的 ZK Rollup 运行&#xff0c;帮助 dApp 使用 STARK 证明以更低的交易成本实现更大的计算规模。该网络允许智能合约与区块链上部署的其他合约进行交互&#xff0c;从而提高协议之间的…
阅读更多...
简单说说vue中v-model和v-bind绑定数据的异同

简单说说vue中v-model和v-bind绑定数据的异同

vue的模板采用DOM模板&#xff0c;也就是说它的模板可以当做DOM节点运行&#xff0c;在浏览器下不报错&#xff0c;绑定数据有三种方式&#xff0c;一种是插值&#xff0c;也就是{{name}}的形式&#xff0c;一种是属性绑定 v-bind&#xff0c;还有一种是双向绑定 v-model。{{na…
阅读更多...
Postman Post请求上传文件

Postman Post请求上传文件

Postman Post请求上传文件 一、选择post请求方式&#xff0c;输入请求地址 二、填写Headers Key&#xff1a;Content-Type Value&#xff1a;multipart/form-data [{"key":"Content-Type","value":"multipart/form-data","de…
阅读更多...
校园局域网规划与设计(cisco仿真模拟）

校园局域网规划与设计(cisco仿真模拟）

摘 要 随着网络技术的发展&#xff0c;校园网的建设已经进入到一个蓬勃发展的阶段。校园网的建成和使用&#xff0c;对于提高教学和科研的质量、改善教学和科研条件、加快学校的信息化进程&#xff0c;开展多媒体教学与研究以及使教学多出人才、科研多出成果有着十分重要而深远…
阅读更多...
深入理解前端路由：构建现代 Web 应用的基石（上）

深入理解前端路由：构建现代 Web 应用的基石（上）

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
Hdoop学习笔记（HDP）-Part.13 安装Ranger

Hdoop学习笔记（HDP）-Part.13 安装Ranger

目录 Part.01 关于HDP Part.02 核心组件原理 Part.03 资源规划 Part.04 基础环境配置 Part.05 Yum源配置 Part.06 安装OracleJDK Part.07 安装MySQL Part.08 部署Ambari集群 Part.09 安装OpenLDAP Part.10 创建集群 Part.11 安装Kerberos Part.12 安装HDFS Part.13 安装Ranger …
阅读更多...
MySQL的系统信息函数

MySQL的系统信息函数

系统信息函数让你更好的使用MySQL数据库 1、version()函数 查看MySQL系统版本信息号 select version();2、connection_id()函数 查看当前登入用户的连接次数 直接调用CONNECTION_ID()函数--不需任何参数--就可以看到当下连接MySQL服务器的连接次数&#xff0c;不同时间段该…
阅读更多...
Jmeter性能测试 —— 压力模式

Jmeter性能测试 —— 压力模式

压力模式 性能测试中的压力模式有两种。 第一种是并发用户模式&#xff08;虚拟用户模式&#xff09;并发用户是指虚拟并发用户数&#xff0c;从业务角度&#xff0c;也可以理解为同时在线的用户数。 从客户端的角度出发&#xff0c;摸底业务系统各节点能同时承载的在线用户数…
阅读更多...
最新文章

Copyright @ 2022~2023