代码随想录leetcode200题之链表

目录

  • 1 介绍
  • 2 训练
  • 3 参考

1 介绍

本博客用来记录代码随想录leetcode200题中链表部分的题目。

2 训练

题目1：203移除链表元素

C++代码如下，

/**
 * 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* removeElements(ListNode* head, int val) {
        ListNode* p = new ListNode(0, head);
        ListNode* res = p;
        while (p->next != nullptr) {
            if (p->next->val == val) p->next = p->next->next;
            else p = p->next;
        }

        return res->next;
    }
};

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        p = ListNode(0, head)
        res = p
        while p.next is not None:
            if p.next.val == val:
                p.next = p.next.next 
            else:
                p = p.next 
        return res.next

题目2：707设计链表

C++代码如下，

// struct ListNode {
//     int val;
//     ListNode* next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode* nx) : val(x), next(nx) {}
// };

class MyLinkedList {
private:
    ListNode* head; //head无实际含义

public:


    MyLinkedList() {
        head = new ListNode(0);
    }
    
    int get(int index) {
        //时间复杂度O(N)
        int i = 0;
        ListNode* p = head->next;
        while (p != nullptr) {
            if (i == index) return p->val;
            p = p->next;
            i += 1;
        }
        return -1;
    }
    
    void addAtHead(int val) {
        //时间复杂度O(1)
        ListNode* p = new ListNode(val, head->next);
        head->next = p; 
    }
    
    void addAtTail(int val) {
        //时间复杂度O(N)
        ListNode* p = head;
        while (p->next != nullptr) p = p->next;
        ListNode* t = new ListNode(val);
        p->next = t;
    }
    
    void addAtIndex(int index, int val) {
        //时间复杂度O(N)
        ListNode* p = head; //p从头结点开始算
        int i = 0;
        while (p != nullptr && i < index) {
            p = p->next;
            i += 1;
        }

        if (p == nullptr) return;

        ListNode* t = new ListNode(val, p->next);
        p->next = t;
    }
    
    void deleteAtIndex(int index) {
        //时间复杂度为O(N)
        ListNode* p = head; //p从头结点开始算
        int i = 0;
        while (p != nullptr && i < index) {
            p = p->next;
            i += 1;
        }

        if (p == nullptr || p->next == nullptr) return;

        p->next = p->next->next;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

python3代码如下，

class MyLinkedList:

    def __init__(self):
        self.head = ListNode(0)


    def get(self, index: int) -> int:
        #时间复杂度为O(N)
        i = 0
        p = self.head.next 
        while p is not None:
            if i == index:
                return p.val 
            p = p.next 
            i += 1
        return -1

    def addAtHead(self, val: int) -> None:
        #时间复杂度为O(1)
        p = ListNode(val, self.head.next)
        self.head.next = p

    def addAtTail(self, val: int) -> None:
        #时间复杂度为O(N)
        p = self.head 
        while p.next is not None:
            p = p.next 
        t = ListNode(val)
        p.next = t 

    def addAtIndex(self, index: int, val: int) -> None:
        #时间复杂为O(N)
        p = self.head 
        i = 0
        while p is not None and i < index:
            p = p.next 
            i += 1
        
        if p is None:
            return 
        
        t = ListNode(val, p.next)
        p.next = t 

    def deleteAtIndex(self, index: int) -> None:
        #时间复杂度为O(N)
        p = self.head 
        i = 0
        while p is not None and i < index:
            p = p.next 
            i += 1
        
        if p is None or p.next is None:
            return 
        
        p.next = p.next.next 



# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

题目3：206. 反转链表

C++代码如下，

/**
 * 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* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) { //特判空集或一个结点的时候
            return head;
        }

        ListNode* a = head;
        ListNode* b = a->next;

        while (a != nullptr && b != nullptr) {
            ListNode* t = b->next;
            b->next = a;

            a = b;
            b = t;
        }
        
        head->next = nullptr;
        return a;
    }
};

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None: #特判空集和一个结点的情况
            return head 

        a = head 
        b = a.next 
        while a is not None and b is not None:
            t = b.next

            b.next = a 

            a = b
            b = t 
        
        head.next = None 
        return a

题目4：24两两交换链表中的节点

C++代码如下，

/**
 * 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* a = head;
        ListNode* b = a->next;

        ListNode* res = b;
        ListNode* aprev = nullptr;

        while (a != nullptr && b != nullptr) {
            ListNode* t = b->next;

            b->next = a;
            a->next = t;
            if (aprev != nullptr) aprev->next = b;

            aprev = a;
            a = t;
            if (a != nullptr) b = a->next;
            else break;
        }

        return res;
    }
};

python3代码如下，

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None: #特判空集或者一个结点的情况
            return head 
        
        a = head 
        b = a.next 
        aprev = None 

        res = b 

        while a is not None and b is not None:
            t = b.next 

            b.next = a 
            a.next = t 
            if aprev is not None:
                aprev.next = b
            
            aprev = a 
            a = t
            if a is not None:
                b = a.next 
            else:
                break
        
        return res

题目5：19删除链表的倒数第 N 个结点

C++代码如下，

/**
 * 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* removeNthFromEnd(ListNode* head, int k) {
        //删除倒数第k个结点，快慢指针法

        ListNode* dummy = new ListNode(0, head);

        ListNode* a = dummy;
        ListNode* b = dummy;

        while (k--) { //b先走k步
            b = b->next;
        }

        while (b->next != nullptr) { //b走到最后一个结点
            a = a->next;
            b = b->next;
        }

        if (a->next != nullptr) a->next = a->next->next;
        else cout << "a->next is nullptr!" << endl;

        return dummy->next;
    }
};

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        a = dummy
        b = dummy 

        while k > 0:
            b = b.next
            k -= 1

        while b.next is not None:
            b = b.next 
            a = a.next 
        
        a.next = a.next.next 
        return dummy.next

题目6：面试题 02.07. 链表相交

C++代码如下，

/**
 * 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) {
        if(headA == nullptr || headB == nullptr) { //特判都为空集，或者有一方为空集的情况
            return nullptr;
        }
        
        ListNode* a = headA;
        ListNode* b = headB;

        bool flaga = true;
        bool flagb = true;
        while (a != b) {
            a = a->next;
            b = b->next;

            if (a == nullptr) {
                if (flaga) {
                    a = headB;
                    flaga = false;
                } else {
                    break;
                }
            }

            if (b == nullptr) {
                if (flagb) {
                    b = headA;
                    flagb = false;
                } else {
                    break;
                }
            }
        }

        if (a == b) return a;
        else return nullptr;
    }
};

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA is None or headB is None:
            return None 
        
        a = headA 
        b = headB 
        flaga = True
        flagb = True 
        while a != b:
            a = a.next 
            b = b.next 

            if a is None:
                if flaga:
                    a = headB 
                    flaga = False
                else:
                    break 
            
            if b is None:
                if flagb:
                    b = headA 
                    flagb = False 
                else:
                    break 
        
        if a == b:
            return a 
        else:
            return None

题目7：142. 环形链表 II

C++代码如下，

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //这次的快慢指针，是速度上的快慢指针，而非提前走的快慢指针
        ListNode* a = head;
        ListNode* b = head;

        while (b != nullptr && b->next != nullptr) {
            a = a->next;
            b = b->next->next;

            //起点到环入口的距离为x
            //快慢指针相遇点到环入口的距离为y
            //环的周长为c
            //有x % c = y恒成立
            if (a == b) { 
                ListNode* t = head;
                while (t != a) {
                    t = t->next;
                    a = a->next;
                }
                return a;
            }
        }
        return nullptr;
    }
};

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        a = head 
        b = head 

        while b is not None and b.next is not None:
            a = a.next 
            b = b.next.next 

            if a == b:
                t = head 
                while t != a:
                    t = t.next 
                    a = a.next 
                return a 
        return None

3 参考

代码随想录官网

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

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

相关文章

PopChar for Mac v10.1激活版：特殊字符输入工具

PopChar for Mac v10.1激活版：特殊字符输入工具

PopChar for Mac是一款专为Mac用户设计的字符输入工具&#xff0c;其简单直观的功能使得查找和插入特殊字符变得轻而易举。 PopChar for Mac v10.1激活版下载 首先&#xff0c;PopChar为Mac提供了访问所有字体字符的能力&#xff0c;包括那些难以通过键盘直接输入的字符。用户只…
阅读更多...
【3dmax笔记】032： 编辑顶点

【3dmax笔记】032： 编辑顶点

一、编辑顶点概述 （1）启动安装好的3dmax软件。 （2）选择顶视图，用图形画出一个矩形。 （3）选择矩形，右击鼠标，将矩形转换成可编辑样条线。 （4）进入顶点层级。 展开可编辑样条线，选择顶点层级（快捷键为1，在不展开样条线的情况下也可以选择顶点层级）。选择后，可以…
阅读更多...
postman介绍、安装、使用、功能特点、注意事项

postman介绍、安装、使用、功能特点、注意事项

Postman是一款流行的API开发工具&#xff0c;它提供了丰富的功能&#xff0c;包括创建、测试、调试和文档化API。本文将介绍Postman的安装、使用方法&#xff0c;以及其功能特点和注意事项。 1. 介绍 Postman是一款用于构建、测试和调试API的工具&#xff0c;它提供了用户友好的…
阅读更多...
串口通信---了解

串口通信---了解

1 串口接线方式 RXD&#xff1a;数据输入引脚&#xff0c;数据接受&#xff1b;STC89系列对应P3.0口 TXD&#xff1a;数据发送引脚&#xff0c;数据发送&#xff1b;STC89系列对应P3.1口 接线方式 串口编程要素 输入/输出数据缓冲器叫做SBUF&#xff0c;都用99H地址码&#x…
阅读更多...
链式二叉树的基本操作1

链式二叉树的基本操作1

1.概念回顾 讲二叉树的基本操作之前&#xff0c;我们回顾一下二叉树的概念 在讲树之前&#xff0c;我们的每讲一种数据结构&#xff0c;无外乎就是在讲它们的增删查改&#xff0c;但是在树这里&#xff0c;就有了不小变化。 2.结点的定义 既然是链式二叉树&#xff0c;那必须…
阅读更多...
必学-设计模式

必学-设计模式

设计模式的分类 创建型模式&#xff08;Creational&#xff09;&#xff1a;关注对象的实例化过程&#xff0c;包括了如何实例化对象、隐藏对象的创建细节等。常见的创建型模式有单例模式、工厂模式、抽象工厂模式等。 结构型模式&#xff08;Structural&#xff09;&#xff…
阅读更多...
Tensorflow2.0笔记 - 循环神经网络RNN做IMDB评价分析

Tensorflow2.0笔记 - 循环神经网络RNN做IMDB评价分析

本笔记记录使用SimpleRNNCell做一个IMDB评价系统情感二分类问题的例子。 import os import time import numpy as np import tensorflow as tf from tensorflow import keras from tensorflow.keras import datasets, layers, optimizers, Sequential, metrics, Inputos.envir…
阅读更多...
VisualGLM-6B微调（V100）

VisualGLM-6B微调（V100）

Visualglm-6b-CSDN博客文章浏览阅读1.3k次。【官方教程】XrayGLM微调实践&#xff0c;&#xff08;加强后的GPT-3.5&#xff09;能力媲美4.0&#xff0c;无次数限制。_visualglm-6bhttps://blog.csdn.net/u012193416/article/details/131074962?ops_request_misc%257B%2522req…
阅读更多...
2. Linux 基本指令(上)|ls|pwd|cd|tree|touch|mkdir|rmdir|rm

2. Linux 基本指令(上)|ls|pwd|cd|tree|touch|mkdir|rmdir|rm

前言 计算机软硬件体系结构 层状结构应用软件Word&#xff0c;Matlab操作系统Windows&#xff0c;Linux设备驱动声卡驱动硬件CPU&#xff0c;内存&#xff0c;磁盘&#xff0c;显示器&#xff0c;键盘 操作系统概念 操作系统 是一款进行软硬件资源管理的软件 例子 比如在学…
阅读更多...
Join优化规则及应用层BI系统实践

Join优化规则及应用层BI系统实践

目录 一、背景 二、查询优化器概述​编辑 2.1 System R Optimizer 2.2 Volcano Optimizer 2.3 Cascade Optimizer 三、Join相关优化规则 3.1 JoinReorder 3.1.1 少量表的Reorder 3.1.2 大量表的Reorder 3.1.3 星型模型的Reorder 3.2 外连接消除 3.3 Join消除 3.4 谓…
阅读更多...
使用ROW_NUMBER()分组遇到的坑

使用ROW_NUMBER()分组遇到的坑

1、再一次清洗数据时&#xff0c;需要过滤重复数据&#xff0c;使用了ROW_NUMBER() 来分组给每组数据排序号 在获取每组的第一行数据 with records as(select cc.F_Id as Id,REPLACE(cc.F_CNKITitle,char(10),1) as F_CNKITitle,REPLACE(REPLACE(cc.F_Special,专题&#xff1…
阅读更多...
适合大学生的鸿蒙开发板-Purple Pi OH之安装Docker

适合大学生的鸿蒙开发板-Purple Pi OH之安装Docker

一、介绍 本文基于purple-pi-oh系列主板演示Linux 系统安装Docker&#xff0c;方法适用于RK3566全系列产品。本教程将指导你在基于RK3566的LInux系统上安装Docker。Docker是一个开放源代码的应用容器引擎&#xff0c;允许开发者打包他们的应用及依赖包到一个可移植的容器中&am…
阅读更多...
【银角大王——Django课程——分页显示功能实现】

【银角大王——Django课程——分页显示功能实现】

分页显示功能实现 添加假数据&#xff0c;然后演示分页功能分页——功能实现基于之前的靓号列表函数添加代码只显示10条——按照等级排序页码list表样式——bootstrap样式显示当前页面——前五页&#xff0c;后五页给当前页添加样式页码bug更改——出现负数&#xff0c;没有数据…
阅读更多...
【neteq】tgcall的调用、neteq的创建及接收侧ReceiveStatisticsImpl统计

【neteq】tgcall的调用、neteq的创建及接收侧ReceiveStatisticsImpl统计

G:\CDN\P2P-DEV\Libraries\tg_owt\src\call\call.cc基本是按照原生webrtc的来的：G:\CDN\P2P-DEV\tdesktop-offical\Telegram\ThirdParty\tgcalls\tgcalls\group\GroupInstanceCustomImpl.cpptg对neteq的使用 worker 线程创建call Call的config需要neteqfactory Call::CreateAu…
阅读更多...
MySQL——变量的浮点数问题处理

MySQL——变量的浮点数问题处理

新建链接&#xff0c;自带world数据库&#xff0c;里面自带city表格。 DQL #MySQL变量的浮点数问题处理 set dx3.14,dy3.25; select dxdy;#计算显示异常&#xff0c;会有很多00000的提示set resultdxdy; select result; 查询结果
阅读更多...
为何预测预测蛋白质结构这么重要AlphaFold 3；阿里巴巴的开源语音转文字；抱抱脸开源LeRobot

为何预测预测蛋白质结构这么重要AlphaFold 3；阿里巴巴的开源语音转文字；抱抱脸开源LeRobot

✨ 1: AlphaFold 3 谷歌DeepMind和同构实验室推出AlphaFold 3 AI模型&#xff0c;旨在精确预测生命分子的结构和相互作用。 AlphaFold 3 是由谷歌DeepMind和Isomorphic Labs开发的一款新型AI模型&#xff0c;它可以以前所未有的精确度预测蛋白质、DNA、RNA、配体&#xff08;…
阅读更多...
【VTKExamples::Rendering】第一期 TestAmbientSpheres（环境照明系数）

【VTKExamples::Rendering】第一期 TestAmbientSpheres（环境照明系数）

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ：870202403 公众号：VTK忠粉 前言 本文分享VTK样例TestAmbientShperes，介绍环境照明系数对Actor颜色的影响，希望对各位小伙伴有所帮助！ 感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！ 你的点赞就是我的动…
阅读更多...
C++：重载、重写与重定义

C++：重载、重写与重定义

一、重载、重写与重定义的概念 C中&#xff0c;重载、重写和重定义是三个与函数和类成员相关的概念&#xff0c;但它们具有不同的含义和用途。 重载&#xff1a;是指在同一作用域内&#xff0c;可以有多个名称相同但参数列表&#xff08;参数类型、参数个数或参数顺序&#x…
阅读更多...
PyCharm安装教程（超详细图文教程)

PyCharm安装教程（超详细图文教程)

一、下载和安装 1.进入PyCharm官方下载&#xff0c;官网下载地址&#xff1a; https://www.jetbrains.com/pycharm/download/ 专业版安装插件放网盘了&#xff0c;网盘下载即可&#xff1a;itcxy.xyz/229.html2.安装 1.下载后找到PyCharm安装包&#xff0c;然后双击双击.ex…
阅读更多...
网工内推 | 技术支持工程师，最高15k，加班有补贴

网工内推 | 技术支持工程师，最高15k，加班有补贴

01 星网信通 招聘岗位&#xff1a;售前技术支持 职责描述&#xff1a; 1、售前技术支持&#xff1a;技术交流、产品选型报价、方案制作等工作&#xff1b; 2、招投标支持&#xff1a;项目招标参数撰写、标书质疑、应标文件技术部分撰写及资质文件归纳准备、现场讲标及技术澄清…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站