【leetcode刷题总结】——代码随想录(链表总结)

代码随想录按照数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构,再从简单刷起,做了几个类型题目之后,再慢慢做中等题目、困难题目。

以下是个人刷题总结,官方网站 https://programmercarl.com/

代码链接:Leetcode-Python: Leetcode-Python

目录

链表理论基础

203.移除链表元素

707.设计链表

206.反转链表

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

19.删除链表的倒数第N个节点

160. 链表相交

142.环形链表II

总结


链表理论基础

什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。

链表的入口节点称为链表的头结点也就是head。

单链表

数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。

双链表

双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

循环链表

循环链表,顾名思义,就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的定义

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

203.移除链表元素

力扣题目链接(opens new window)

题意:删除链表中等于给定值 val 的所有节点。

示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]

示例 2: 输入:head = [], val = 1 输出:[]

示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]

这里添加虚拟节点的方法

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        # 添加虚拟节点
        dummy_head = ListNode(next=head)
        cur = dummy_head
        while cur.next is not None:
            # 判断要删除的节点
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
            return dummy_head.next

非常简单。最后要返回dummy_head.next。

707.设计链表

力扣题目链接(opens new window)

题意:

在链表类中实现这些功能:

  • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
  • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
  • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

这题有点长、可以进行拆分。

这道题目设计链表的五个接口:

  • 获取链表第index个节点的数值
  • 在链表的最前面插入一个节点
  • 在链表的最后面插入一个节点
  • 在链表第index个节点前面插入一个节点
  • 删除链表的第index个节点

可以说这五个接口,已经覆盖了链表的常见操作,是练习链表操作非常好的一道题目

class MyLinkedList(object):

    def __init__(self):
        self.head = Node()
        self.size = 0  # 设置一个链表长度的属性,便于后续操作,注意每次增和删的时候都要更新

    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.size:
            return -1
        cur = self.head.next
        while index:
            cur = cur.next
            index -= 1
        return cur.val

    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        # 新建新节点,将值置为val
        new_node = Node(val)
        # 头插法
        new_node.next = self.head.next
        self.head.next = new_node
        self.size += 1

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        new_node = Node(val)
        cur = self.head
        # 只要链表的next不为空,遍历到最后的位置
        while cur.next:
            cur = cur.next
        # 在最后的位置插入元素 尾插法
        cur.next = new_node
        # 添加成功 链表长度+1
        self.size += 1

    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        在指定位置添加链表元素
        """
        # 如果index<0 选择头插法
        if index < 0:
            self.addAtHead(val)
            return
        # 尾插法
        elif index == self.size:
            self.addAtTail(val)
            return
        # 不存在
        elif index > self.size:
            return

        node = Node(val)
        pre = self.head
        while index:
            pre = pre.next
            index -= 1
        node.next = pre.next
        pre.next = node
        self.size += 1

    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        if index < 0 or index >= self.size:
            return
        pre = self.head
        while index:
            pre = pre.next
            index -= 1
        pre.next = pre.next.next
        self.size -= 1

206.反转链表

力扣题目链接(opens new window)

题意:反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

#思路

如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费

其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:

首先定义一个cur指针,指向头结点,再定义一个pre指针,初始化为null。

然后就要开始反转了,首先要把 cur->next 节点用tmp指针保存一下,也就是保存一下这个节点。

为什么要保存一下这个节点呢,因为接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。

接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。

最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 申请两个指针,第一个指针叫 pre,最初是指向 null 的。
        pre = None
        # 第二个指针 cur 指向 head,然后不断遍历 cur
        cur = head
        # 每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。
        while cur is not None:
            # 记录当前节点的下一个节点
            tmp = cur.next
            # 当前节点指向pre
            cur.next = pre
            # pre和cur节点都前进一位
            pre = cur
            cur = tmp
        return pre

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

力扣题目链接(opens new window)

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        # 初始时,cur指向虚拟头结点
        newHead = head.next
        head.next = self.swapPairs(newHead.next)
        newHead.next = head
        return newHead

# 时间复杂度:O(n)
# 空间复杂度:O(1)

19.删除链表的倒数第N个节点

力扣题目链接(opens new window)

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        # 保存链表的长度
        len = 0
        cur = head
        while cur:  # 求链表的长度
            cur = cur.next
            len += 1

        # 添加虚拟节点
        dummy_head = ListNode(next=head)
        cur = dummy_head
        delect = 0
        while cur.next is not None:
            delect += 1
            # 判断要删除的节点
            if delect == len - n:
                cur.next = cur.next.next
            else:
                cur = cur.next
            return dummy_head.next


if __name__ == '__main__':
    sol = Solution()
    head = None
    for i in [4, 3, 2, 1, 0]:
        head = ListNode(i, head)
    t = 2
    print(sol.removeNthFromEnd(head, t))

160. 链表相交

力扣题目链接(opens new window)

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

# — coding: utf-8 –

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        # if not headA or not headB:
        #     return None
        # pa, pb = headA, headB
        # while pa != pb:
        #     if pa is None:
        #         pa = headB
        #     else:
        #         pa = pa.next
        #     if pb is None:
        #         pb = headA
        #     else:
        #         pb = pb.next
        # return pa

        # 我们求出两个链表的长度,并求出两个链表长度的差值,然后让curA移动到,和curB 末尾对齐的位置
        lenA, lenB = 0, 0
        cur = headA
        while cur:         # 求链表A的长度
            cur = cur.next
            lenA += 1
        cur = headB
        while cur:         # 求链表B的长度
            cur = cur.next
            lenB += 1
        # 搞俩个头
        curA, curB = headA, headB
        # 交换俩个头,让curB为最长链表的头,lenB为其长度
        if lenA > lenB:
            curA, curB = curB, curA
            lenA, lenB = lenB, lenA
        # 让curA和curB在同一起点上(末尾位置对齐)
        for _ in range(lenB - lenA):
            curB = curB.next
        #  遍历curA 和 curB,遇到相同则直接返回
        while curA:
            if curA == curB:
                return curA
            else:
                curA = curA.next
                curB = curB.next
        return None

142.环形链表II

力扣题目链接(opens new window)

题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

 可以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow, fast = head, head
        while fast and fast.next:
            # 慢指针一次移动一个,快指针一次移动两个
            slow = slow.next
            fast = fast.next.next
            # 相遇
            if slow == fast:
                index1 = head
                index2 = slow
                while index2 != index1:
                    index1 = index1.next
                    index2 = index2.next
                # 返回相交的指针
                return index1

总结

  • 链表的种类主要为:单链表,双链表,循环链表
  • 链表的存储方式:链表的节点在内存中是分散存储的,通过指针连在一起。
  • 链表是如何进行增删改查的。
  • 数组和链表在不同场景下的性能分析。

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

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

相关文章

Python初学小知识(十四):数据分析处理库Pandas

Python初学小知识&#xff08;十四&#xff09;&#xff1a;数据分析处理库Pandas 十八 Pandas1 文件读取1.1 读取csv1.2 读取txt1.3 读取excel&#xff08;xlsx&#xff09; 2 内容读取2.1 读取行2.2 读取列 3 数据处理3.1 加减乘除3.1.1 列 与 元素3.1.2 列 与 列 3.2 最值、…

张驰咨询:突破瓶颈降低成本-精益生产咨询的实践策略

在现代企业运营中&#xff0c;提高效率、优化流程是实现成功的关键因素之一。为了帮助企业在这方面取得突破性的进展&#xff0c;精益生产咨询成为了一种备受推崇的方法。本文将介绍精益生产咨询的基本原理、优势以及如何将其应用于企业实践中。 精益生产咨询是一种源于丰田生…

lwIP更新记02:网络接口标志(一个标志只做一件事)

从 lwIP-2.0.0 开始&#xff0c;网络接口 netif 的 up 标志修改为管理标志&#xff0c;up标志不再具有以前的 IP4 地址有效 含义。 什么是网络接口 netif &#xff1f; 网络接口 属于链路层范畴&#xff0c;它旨在对具体网络硬件、软件进行统一封装&#xff0c;并为协议栈上层&…

【运维知识进阶篇】集群架构-Nginx反向代理详解

在互联网请求中&#xff0c;客户端通常无法直接向服务端发起请求&#xff0c;就需要用代理服务&#xff0c;来实现客户端和的交互&#xff0c;起到一个中介的作用。 Nginx代理服务常见模式 Nginx代理按照应用场景模式可以分为正向代理和反向代理。 正向代理是内部上网过程中&a…

实现取关和关注功能

将关注过的用户id存如数据库中 //关注或者取关 Override public Result follow(Long id, Boolean flag) { //1.获取当前登录用户的id UserDTO user UserHolder.getUser(); if(usernull){ return Result.fail("请先登录"); } Long userId user.getId(); //2.判断是关…

关于ubuntu20.04 apt 安装源中搜索不到最新版本gcc 12的问题

一、问题描述 最近在搞Open 3d 点云point cloud 相关的东西&#xff0c;过程需要安装较高版本的cmake 3.20版本以上&#xff0c;3.20版本又需要gcc 更高版本 至少11.0以上&#xff0c;理论上本机配置的有 ubuntu 官方的源和阿里云的源&#xff0c;不过 通过搜索就只能搜索安装的…

微信小程序xr-frame实现交互(地月案例)

基础知识&#xff1a; 1.轮廓 如果想要与场景中的物体进行互动&#xff0c;比如说点击、拖拽物体&#xff0c;那么这个物体得先拥有一个轮廓才行。轮廓是一个组件。与某个物体互动&#xff0c;实际上是在与这个物体的轮廓进行互动&#xff0c;轮廓让这个物体在物理世界中拥有…

WordPress 如何开启多站点 含Apache和Nginx伪静态规则

WordPress 3.0以上的版本支持直接开启多站点模式,这样一来,你可以在一个后台切换多个站点进行管理。 最近打算折腾一个主题演示站,给每个主题使用独立的子站点来搭建演示,如果是Apache环境,配置就比较容易,但是倡萌使用的是 Nginx,花了大量的时间测试了N多网络上的伪静…

Weblogic SSRF 漏洞(CVE-2014-4210)

SSRF漏洞 ​ SSRF&#xff08;服务端请求伪造&#xff09;&#xff0c;指的是攻击者在未能取得服务器所有权限时&#xff0c;利用服务器漏洞以服务器的身份发送一条构造好的请求给服务器所在内网。SSRF攻击通常针对外部网络无法直接访问的内部系统。 ​ 简单的说就是利用一个可…

Jenkins的持续集成与持续部署

系统总体架构 Gitlab Gitlab是一款主要用于代码管理的工具&#xff0c;相较于GitHub&#xff0c;可以自己搭建服务器&#xff0c;这可以避免因为网络速度慢导致部署效率低下&#xff0c;同时&#xff0c;自己搭建服务器&#xff0c;安全性更高。Jenkins Jenkins主要用于管理版本…

国内免费版ChatGPT

目录 前言&#xff1a;网站大全 1. ChatGPT是什么 2. ChatGPT的发展历程 3. ChatGPT对程序员的影响 4. ChatGPT对普通人的影响 5. ChatGPT的不足之处 前言&#xff1a;网站大全 AI文本工具站 (laicj.cn) ——gpt-3.5 功能强大(推荐&#xff09; Chatgpt在线网页版-…

Compose For Desktop 实践:使用 Compose-jb 做一个时间水印助手

前言 在我之前的文章 在安卓中实现读取Exif获取照片拍摄日期后以水印文字形式添加到照片上 中&#xff0c;我们已经实现了在安卓端读取 Exif 信息后添加文字水印到图片上。 也正如我在这篇文章中所说的&#xff0c;其实这个需求使用手机来实现是非常不合理的&#xff0c;一般…

jenkins入门与安装

一、实验环境 selinux iptables off 主机名IP系统版本gitlab10.10.10.200rhel7.5jenkins10.10.10.10rhel7.5tomcat10.10.10.11rhel7.5 二、安装jenkins 1、解压安装包 下载地址&#xff1a;https://download.docker.com/linux/static/stable/x86_64/ [rootjenkins ~]# tar xf …

视频截取动图怎么做?分享在线视频转gif小窍门

如何将一段视频制作成gif动图表情包呢&#xff1f;Gif表情包常见的制作方法就是将电影、电视剧中的某个画面截取出来做成gif表情包。那么&#xff0c;如何从视频中截取GIF呢&#xff1f; 一、怎样才能完成视频转gif制作&#xff1f; 通过使用GIF中文网的视频转gif&#xff08…

RT-Thread 1. GD32移植RT-Thread Nano

1. RT-Thread Nano 下载 RT-Thread Nano 是一个极简版的硬实时内核&#xff0c;它是由 C 语言开发&#xff0c;采用面向对象的编程思维&#xff0c;具有良好的代码风格&#xff0c;是一款可裁剪的、抢占式实时多任务的 RTOS。其内存资源占用极小&#xff0c;功能包括任务处理…

多维时序 | MATLAB实现CNN-BiGRU卷积神经网络结合双向门控循环单元多变量时间序列预测

多维时序 | MATLAB实现CNN-BiGRU卷积神经网络结合双向门控循环单元多变量时间序列预测 目录 多维时序 | MATLAB实现CNN-BiGRU卷积神经网络结合双向门控循环单元多变量时间序列预测预测结果基本介绍模型特点程序设计学习总结参考资料 预测结果 基本介绍 多维时序 | MATLAB实现CN…

字符串String

目录 String 字符串比较 charAt 取数组中的值 案例 substring 案例&#xff1a;手机号加密​ StringBuilder StringBuilder提高效率原理图 StringJoiner 字符串拼接底层方法 String 创造方法 直接赋值通过new关键字 / 构造方法 字符串比较 equals &#xff1a;要求比…

小白安装 stabel diffusion 篇

windows 系统安装 stabel diffusion 软件的方法其实很简单&#xff0c;只有 4 步&#xff08;安装过程遇到的报错问题&#xff0c;本文有详细的解决方案&#xff0c;都是我踩过的坑&#xff0c;给大家探路了&#xff09;&#xff1a; 1、安装 python&#xff08;建议安装 3.10…

Spark 2:Spark Core RDD算子

RDD定义 RDD&#xff08;Resilient Distributed Dataset&#xff09;叫做弹性分布式数据集&#xff0c;是Spark中最基本的数据抽象&#xff0c;代表一个不可变、可分区、里面的元素可并行计算的集合。 Resilient&#xff1a;RDD中的数据可以存储在内存中或者磁盘中。 Distribut…

玩客云刷NAS

测试路由器支持IPV6 参考 这里 我用的是TPlink WDR7660 支持IPV6 主要设置桥模式 玩客云刷写固件 参考 这里 还有这里 玩客云固定IP 参考这里 sudo armbian-config 选择Network 选择有线网络->ip 选择static 然后根据自己情况进行设置 点击OK即可 更新国内源 参考这里 证书…