leetcode链表相关题目

文章目录

  • 1.移除链表元素
    • 方法1：
    • 方法2
  • 2.合并两个有序链表
  • 3.链表的中间节点
    • 方法1
    • 方法2
  • 4.反转单链表
    • 方法1
    • 方法2
  • 5.分割链表
  • 6.链表中的倒数第k个节点
    • 方法1：
    • 方法2:
  • 7.环形链表的约瑟夫问题
  • 8.链表的回文结构
  • 9.相交链表
    • 方法1
    • 方法2：
  • 10.环形链表
  • 11.环形链表Ⅱ
  • 12.随机链表的复制

在这里插入图片描述
链表学习完以后，来做点相关题目吧

1.移除链表元素

在这里插入图片描述

方法1：

在原链表的基础上直接删除指定元素

  • 若当前节点是要删除的节点，则将其前驱节点指向当前节点的下一个节点
  • 若当前节点不是要删除的节点，前驱节点指向当前节点，当前节点后移
  • 特殊情况：
    • 循环判断，若头节点是要删除的节点，则将头节点后移
    • 头节点不为空
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* prev = head;
    //判断头节点
    while(head && head->val == val)
    {
        head = head->next;
    }
    //链表为空
    if(head == NULL)
    {
        return NULL;
    }
    //正常情况
    while(cur)
    {
        if(cur->val == val)
        {
            prev->next = cur->next;
        }
        else
        {
            prev = cur;
        }
        cur =  cur->next;
    }
    return head;
}

方法2

创建一个新的链表存放未删除的元素

  • 先创建一个虚拟的头节点，指向新链表，同时记录该链表的尾
  • 若当前节点是要删除的元素，直接后移
  • 若当前节点不是要删除的元素，连接到新链表的尾后
  • 将新链表尾节点的next置为空（断开与原链表的连接）
struct ListNode* removeElements(struct ListNode* head, int val) {
    //设置新链表的头
    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->val = -1;
    newhead->next = NULL;
    struct ListNode* cur = head;
    struct ListNode* tail = newhead;
    while(cur)
    {
        if(cur->val == val)
        {
            cur = cur->next;
        }
        else
        {
            tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
    }
    //将新链表与原链表断开
    tail->next = NULL;
    struct ListNode* ret = newhead->next;
    free(newhead);
    newhead = tail = NULL;
    return ret;
}

2.合并两个有序链表

在这里插入图片描述

创建一个新的链表

  • 两个指针分别指向两个链表
  • 将两指针所指向的元素的较小值连接到新链表的尾
  • 若有一个指针走到空，则将另一个指针连接到新链表的尾
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //定义新链表的头
    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->val = -1;
    newhead->next = NULL;

    struct ListNode* tail = newhead;
    //比较链表元素
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    //若有一个链表为空，则连接另一个
    if(list1)
    {
        tail->next = list1;
    }
    else
    {
        tail->next = list2;
    }
    struct ListNode* ret = newhead->next;
    free(newhead);
    newhead = tail = NULL;
    return ret;
}

3.链表的中间节点

在这里插入图片描述

方法1

统计链表长度，计算出中间位置；再寻找中间位置

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* cur = head;
    int len = 0;
    while(cur)
    {
        len++;
        cur = cur->next;
    }
    int count = 0;
    cur = head;
    while(count < (len / 2))
    {
        count++;
        cur = cur->next;
    }
    return cur;
}

方法2

快慢指针法：一个指针一次走一步，一个指针一次走两步。当快指针尾空或者快指针的next为空，那么慢指针所指向的元素就是中间元素。
在这里插入图片描述

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

4.反转单链表

在这里插入图片描述

方法1

定义一个新的头节点，然后遍历链表，采取头插
在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newHead->val = -1;
    newHead->next = NULL;

    while(head)
    {
        //先记录后继节点
        struct ListNode* next = head->next;
        //头插
        head->next = newHead->next;
        newHead->next = head;
        //节点后移
        head = next;
    }
    return newHead->next;
}

方法2

原地直接反转

  • 先记录当前节点的后继节点，以便节点后移
  • 当前节点指向其前驱节点
  • 前驱节点后移
  • 当前节点后移
  • prev即为反转后新的头

在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* next = NULL;
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;

    while(cur)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

5.分割链表

在这里插入图片描述
思路：

  • 给定两个新的链表，一个放小于X的元素，一个放大于X的元素
  • 元素尾插至新链表
  • 将两个新链表相连

在这里插入图片描述

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* minHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* maxHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* minTail = minHead;
    struct ListNode* maxTail = maxHead;
    struct ListNode* cur = head;

    while(cur)
    {
        if(cur->val < x)
        {
            minTail->next = cur;
            minTail = minTail->next;
        }
        else
        {
            maxTail->next = cur;
            maxTail = maxTail->next;
        }
        cur = cur->next;
    }
    //防止成环
    maxTail->next = NULL;
    minTail->next = maxHead->next;
    struct ListNode* ret = minHead->next;
    free(minHead);
    free(maxHead);
    return ret;
}

6.链表中的倒数第k个节点

在这里插入图片描述

方法1：

思路：倒数第k就是正数第n-k+1个（n为链表长度）
特殊情况：

  • k应该小于链表长度
  • k不能为0
  • 链表不能为空
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    struct ListNode* cur = pListHead;
    int len = 0;
    //求链表的长度
    while (cur)
    {
        len++;
        cur = cur->next;
    }
    //特殊情况判断
    //1.k不能大于链表长度
    //2.k不能为0
    //3.链表不为空
    if (k > len || k == 0 || pListHead == NULL)
    {
        return NULL;
    }
    //倒数第k个就是正数第n-k+1个
    int n = 1;
    len = len - k + 1;
    cur = pListHead;
    while (n != len)
    {
        n++;
        cur = cur->next;
    }
    return cur;
}

方法2:

快慢指针：快指针先走k步，然后快慢一起走
在这里插入图片描述

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    //快指针先走k步
    while(k--)
    {
        //fast不能走出链表（k符合）
        if(fast)
        {
            fast = fast->next;
        }
        else 
        {
            return NULL;
        }
    }
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

7.环形链表的约瑟夫问题

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

  • 构建环形链表，给每个节点编号
  • 逢m就删除节点，再从新报数

在这里插入图片描述

typedef struct ListNode  ListNode;

//创建节点
ListNode* CreatNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

//构建环
ListNode* CreatCircle(int n)
{
    ListNode* head = CreatNode(1);
    ListNode* tail = head;
    //连续创建节点
    for(int i=2; i<=n; i++)
    {
        ListNode* newnode = CreatNode(i);
        //连接节点
        tail->next = newnode;
        tail = tail->next;
    }
    //成环
    tail->next = head;
    //返回尾节点的目的是：防止第一个元素就是要删除的元素
    return tail;
}

int ysf(int n, int m ) {
    ListNode* prev = CreatCircle(n);
    ListNode* cur = prev->next;
    int count = 1;
    //有多个节点继续报数，直到剩下一个节点
    while(cur->next != cur)
    {
        //逢m就删除
        if(count == m)
        {
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
            count = 1;
        }
        else 
        {
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
    return cur->val;
}

8.链表的回文结构

在这里插入图片描述
思路：从链表的中间节点逆置后半段，然后比较前半段与后半段是否相等。

  • 快慢指针找链表的中间节点
  • 从中间节点反转单链表
  • 节点比较

在这里插入图片描述
在这里插入图片描述

	//找中间节点
    ListNode* FindMid(ListNode* A)
    {
        ListNode* fast = A;
        ListNode* slow = A;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;   
    }
	//反转
    ListNode* Reverse(ListNode* mid)
    {
        ListNode* cur = mid;
        ListNode* prev = NULL;
        ListNode* next = NULL;
        while(cur)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    bool chkPalindrome(ListNode* A) {
        ListNode* mid = FindMid(A);
        ListNode* midhead = Reverse(mid);

        while(midhead)
        {
            if(A->val == midhead->val)
            {
                A = A->next;
                midhead = midhead->next;
            }
            else 
            {
                return false;
            }
        }
        return true;
    }

9.相交链表

在这里插入图片描述

方法1

将链表A中的每一个节点与链表B中的每一个节点比较，看是否相等。

  • 若相等，则返回相等的节点
  • 若所有节点都不相等，则链表不相交。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    while(curA)
    {
        curB = headB;
        while(curB)
        {
            //若节点相等，直接返回相等节点
            if(curA == curB)
            {
                return curA;
            }
            curB = curB->next;
        }
        curA = curA->next;
    }
    //A中每一个节点都与B比较完毕，仍无交点
    return NULL;
}

方法2：

分别计算两链表长度，长的先走长度差步，然后再一起走，判断是否相等。

  • 再求链表长度的同时，若两链表的最后一个节点相等，则二者一定相交
struct ListNode* getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0;
    int lenB = 0;
    //先计算链表各自的长度，都少计算一个
    while(curA->next)
    {
        lenA++;
        curA = curA->next;
    }
    while(curB->next)
    {
        lenB++;
        curB = curB->next;
    }
    //若不相交，直接返回空
    if(curA != curB)
    {
        return NULL;
    }
    //算长度差
    int  gap = abs(lenA - lenB);
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
    //长的先走长度差步
    while(gap--)
    {
        longList = longList->next;
    }
    //同时走，找交点
    while(longList && shortList)
    {
        if(longList == shortList)
        {
            return shortList;
        }
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}

10.环形链表

在这里插入图片描述
思路：快慢指针。

  • 一个指针一次走一步，一个指针一次走两步
  • 若快指针走到了空，则不带环
  • 若快指针与慢指针相遇，则带环
bool hasCycle(struct ListNode *head) {
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}

为什么这样可以呢?
在这里插入图片描述

为什么不是一个走1步一个走3步？一个走1步一个走4步？一个走1步一个走6步？…

在这里插入图片描述
在这里插入图片描述

若N为奇数，C-1也为奇数则永远追不上（存在这种情况吗？）

在这里插入图片描述
所以，一步两步走是最保险也是最简单的方式，不会错过。

11.环形链表Ⅱ

在这里插入图片描述
思路：快慢指针，找到二者的相遇点。再使用两指针，从相遇点和链表头开始走，二者相遇点就是入环点

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;

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

原理

在这里插入图片描述

12.随机链表的复制

在这里插入图片描述
在这里插入图片描述
本题的难点在于random的指向难以找到
思路：

  • 在原链表每个节点的后面尾插一个新的节点
  • 根据原链表，找到新链表的random指向
  • 将新链表的节点与原链表分离，恢复原链表

第一步：连接新节点
在这里插入图片描述

第二步：搞清random指向
新链表random就是原链表random的next!!!
在这里插入图片描述
第三步：将新链表从原链表上摘下来
在这里插入图片描述

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    //插入新节点
    while(cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        //连接新节点
        newnode->val = cur->val;
        newnode->next = cur->next;
        cur->next = newnode;
        //原链表后移
        cur = cur->next->next;
    }
    //random
    cur = head;
    while(cur)
    {
        struct Node* newnode = cur->next;
        if(cur->random == NULL)
        {
            newnode->random = NULL;
        }
        else
        {
            newnode->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //摘新链表
    struct Node* newhead = (struct Node*)malloc(sizeof(struct Node));
    newhead->next = NULL;
    newhead->random = NULL;
    struct Node* tail = newhead;
    cur = head;
    while(cur)
    {
        //尾插新链表
        struct Node* newnode = cur->next;
        tail->next = newnode;
        tail = tail->next;
        //恢复原链表
        cur->next = newnode->next;

        cur = cur->next;
    }
    return newhead->next;
}

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

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

相关文章

python接口自动化（三）--如何设计接口测试用例（详解）

python接口自动化（三）--如何设计接口测试用例（详解）

在开始接口测试之前&#xff0c;我们来想一下&#xff0c;如何进行接口测试的准备工作。或者说&#xff0c;接口测试的流程是什么&#xff1f;有些人就很好奇&#xff0c;接口测试要流程干嘛&#xff1f;不就是拿着接口文档直接利用接口 测试工具测试嘛。其实&#xff0c;如果…
阅读更多...
关于物理机ping不通虚拟机问题

关于物理机ping不通虚拟机问题

方法一 设置虚拟机处于桥接状态即可&#xff1a;&#xff08;虚拟机->设置->网络适配器&#xff09;&#xff0c;选择完确定&#xff0c;重启虚拟机即可。 方法二 如果以上配置还是无法ping通&#xff1a;&#xff08;编辑->虚拟网络编辑器&#xff09; 首先查看主机网…
阅读更多...
MySQL（基础）

MySQL（基础）

第01章_数据库概述 1. 为什么要使用数据库 持久化(persistence)&#xff1a;把数据保存到可掉电式存储设备中以供之后使用。大多数情况下&#xff0c;特别是企业级应用&#xff0c;数据持久化意味着将内存中的数据保存到硬盘上加以”固化”&#xff0c;而持久化的实现过程大多…
阅读更多...
C++11中的简化声明

C++11中的简化声明

auto 用于自动类型推断&#xff0c;显示定义变量&#xff1a; typeid typeid推导出来的是字符串&#xff0c;只能看不能用&#xff0c;通过打印来查看变量的类型&#xff0c;用法如上。 decltype 同样是用来自动推导类型&#xff0c;与auto的区别是&#xff0c;auto在定义时必…
阅读更多...
DAY9.

DAY9.

1.选择芯片型号 2. 3. 4. 5. 6. 7.
阅读更多...
MOCO动量编码

MOCO动量编码

参考&#xff0c;推荐阅读 李沐论文精读系列三&#xff1a;MoCo、对比学习综述&#xff08;MoCov1/v2/v3、SimCLR v1/v2、DINO等&#xff09;_moco 对比学习-CSDN博客 背景 1. MOCO CVPR 2020 2. 对比学习&#xff1a;无监督学习的一种&#xff0c;重点学习同类实例中的共同…
阅读更多...
第78讲 修改密码

第78讲 修改密码

系统管理实现 修改密码实现 前端 modifyPassword.vue&#xff1a; <template><el-card><el-formref"formRef":model"form":rules"rules"label-width"150px"><el-form-item label"用户名&#xff1a;&quo…
阅读更多...
网络安全的今年：量子、生成人工智能以及 LLM 和密码

网络安全的今年：量子、生成人工智能以及 LLM 和密码

尽管世界总是难以预测&#xff0c;但网络安全的几个强劲趋势表明未来几个月的发展充满希望和令人担忧。有一点是肯定的&#xff1a;2024 年将是非常重要且有趣的一年。 近年来&#xff0c;人工智能&#xff08;AI&#xff09;以令人难以置信的速度发展&#xff0c;其在网络安全…
阅读更多...
Vue源码系列讲解——虚拟DOM篇【四】(优化更新子节点)

Vue源码系列讲解——虚拟DOM篇【四】(优化更新子节点)

目录 1. 前言 2. 优化策略介绍 3. 新前与旧前 4. 新后与旧后 5. 新后与旧前 6. 新前与旧后 7. 回到源码 8. 总结 1. 前言 在上一篇文章中&#xff0c;我们介绍了当新的VNode与旧的oldVNode都是元素节点并且都包含子节点时&#xff0c;Vue对子节点是 先外层循环newChil…
阅读更多...
Illegal escape character in string literal

Illegal escape character in string literal

问题 笔者进行Android项目开发&#xff0c;编译器提示报错 Illegal escape character in string literal详细问题 textView.setText(“A\B”); 解决方案 修改代码为A\B textView.setText(“A\B”) 产生原因 问题产生的原因是在字符串字面值中使用了非法的转义字符。在…
阅读更多...
1978-2023年全国国内生产总值、分产业分行业增加值相关指标数据

1978-2023年全国国内生产总值、分产业分行业增加值相关指标数据

1978-2023年全国国内生产总值、分产业分行业增加值相关指标数据 1、时间&#xff1a;1978-2023年 2、指标&#xff1a;国内生产总值(亿元)、第一产业增加值(亿元)、第二产业增加值(亿元)、第三产业增加值(亿元)、人均国内生产总值(元)、国民总收入指数(上年100)、国内生产总值…
阅读更多...
C++入门学习（二十七）跳转语句—continue语句

C++入门学习（二十七）跳转语句—continue语句

当在循环中遇到continue语句时&#xff0c;它会跳过当前迭代剩余的代码块&#xff0c;并立即开始下一次迭代。这意味着continue语句用于跳过循环中特定的执行步骤&#xff0c;而不是完全终止循环。 直接看一下下面的代码更清晰&#xff1a; 与上一节的break语句可以做一下对比…
阅读更多...
正则表达式与正则可视化工具：解密文本处理的利器

正则表达式与正则可视化工具：解密文本处理的利器

正则表达式与正则可视化工具&#xff1a;解密文本处理的利器 引言 在计算机科学和软件开发领域&#xff0c;正则表达式是一种强大而灵活的文本处理工具。然而&#xff0c;对于初学者来说&#xff0c;正则表达式的语法和规则可能会显得晦涩难懂。为了帮助初学者更好地理解和学…
阅读更多...
Linux---网络套接字

Linux---网络套接字

端口号 端口号 端口号是一个2字节16位的整数; 端口号用来标识一个进程, 告诉操作系统, 当前的这个数据要交给哪一个进程来处理; IP地址 端口号能够标识网络上的某一台主机的某一个进程; 一个端口号只能被一个进程占用 在公网上&#xff0c;IP地址能表示唯一的一台主机&…
阅读更多...
新年福利：《YOLO目标检测》送书活动

新年福利：《YOLO目标检测》送书活动

博主简介 AI小怪兽&#xff0c;YOLO骨灰级玩家&#xff0c;1&#xff09;YOLOv5、v7、v8优化创新&#xff0c;轻松涨点和模型轻量化&#xff1b;2&#xff09;目标检测、语义分割、OCR、分类等技术孵化&#xff0c;赋能智能制造&#xff0c;工业项目落地经验丰富&#xff1b; …
阅读更多...
12.atoi函数

12.atoi函数

文章目录 函数简介函数原型 代码运行 函数简介 函数原型 int atoi(char const *string);函数把字符转化为正数 代码运行 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h>int main() {int ret 0;char str[20] "112233";ret …
阅读更多...
算法竞赛进阶指南——基本算法（倍增）

算法竞赛进阶指南——基本算法（倍增）

ST表 可以求区间最大、最小、gcd、lcm&#xff0c;符合 f(a, a) a都可以 求区间最值&#xff0c;一个区间划分成两段 f[i][j]: 从i开始&#xff0c;长度为2^j的区间最值 #include<iostream> #include<cmath> using namespace std; const int N 1e6 10; int n,…
阅读更多...
如何把手机平板变为电脑的屏幕

如何把手机平板变为电脑的屏幕

文章目录 安装软件运行效果结尾 本文首发地址 https://h89.cn/archives/181.html 最新更新地址 https://gitee.com/chenjim/chenjimblog 闲置的手机平板、触屏音箱等&#xff0c;均可作为电脑的扩展屏&#xff0c;为电脑增加一块显示屏&#xff0c;本文介绍如何使用免费的软件s…
阅读更多...
WordPress后台编辑个人资料页面直接修改用户名插件Change Username

WordPress后台编辑个人资料页面直接修改用户名插件Change Username

前面跟大家介绍了『如何修改WordPress后台管理员用户名&#xff1f;推荐2种简单方法』一文&#xff0c;但是对于新站长或者有很多用户的站长来说&#xff0c;操作有点复杂&#xff0c;所以今天向大家推荐一款可以直接在WordPress后台编辑个人&#xff08;用户&#xff09;资料页…
阅读更多...
C语言辨析——声明int a[3][6], a[0][9]越界吗？

C语言辨析——声明int a[3][6], a[0][9]越界吗？

本文来源&#xff1a;声明int a[3][6], a[0][9]越界吗&#xff1f; 1. 问题 看下面的程序&#xff1a; #include <stdio.h> int main(void) {int a[3][6];for(int i0; i<3; i) {for(int j0; j<6; j){a[i][j] i * 6 j;}}printf("%d\n",a[0][9]);retu…
阅读更多...
最新文章

Copyright @ 2022~2023