当前位置： 首页 > article >正文

【题目】链表相关算法题

article 2024/11/17 8:23:59

文章目录

  • 一. 合并两个有序链表
    • 题目解析
    • 算法原理
    • 代码编写
  • 二. 相交链表问题
    • 题目解析
    • 算法原理
    • 代码编写
  • 三. 环形链表问题
    • 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;
    }
};

http://www.kler.cn/a/154708.html

相关文章：

  • Java基础——多线程
  • 【优选算法 — 滑动窗口】水果成篮 找到字符串中所有字母异位词
  • 【从零开始的LeetCode-算法】3270. 求出数字答案
  • 【Pikachu】任意文件上传实战
  • 【Java基础知识系列】之Java类的初始化顺序
  • Flutter下拉刷新上拉加载的简单实现方式二
  • Beta冲刺总结随笔
  • 论文编写软件latex安装教程
  • Linux: 退出vim编辑模式
  • Scrapy框架内置管道之图片视频和文件(一篇文章齐全)
  • KNN实战-图像识别
  • 禁止谷歌浏览器自动更新
  • XIAO ESP32S3之SenseCraft 模型助手部署
  • C++标准模板（STL）- 类型支持 （杂项变换，定义适于用作给定大小的类型的未初始化存储的类型，std::aligned_storage）
  • 西南科技大学模拟电子技术实验五（集成运算放大器的应用设计）预习报告
  • 计算机网络扫盲（1）——因特网
  • 树莓派搭建开发环境
  • 业余做UE开发顾问
  • Screenshot To Code
  • 安卓底部导航栏BottomNavigationView
  • 云原生高级--shell自动化脚本备份
  • 固定Microsoft Edge浏览器的位置设置，避免自动回调至中国
  • Dart编程基础 - 一种新的编程语言
  • vmware系列：【VMware篇】8-vCenter的安装与配置（一）以IP地址安装
  • Eaxyx 让圆球跟随鼠标移动
  • 《功能磁共振多变量模式分析中空间分辨率对解码精度的影响》论文阅读