链表-基础训练（二）链表 day14

news/2025/2/23 16:03:56

链表中的节点">两两交换链表中的节点

题目示意：

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

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

原先我的思路是图像上的思路，但是我感觉还是很复杂，

思路1：

原代码：
class ListNode:
    def __init__(self,data=0,next=None):
        self.value = data
        self.next = next
class MylinkList:
    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def addAtHead(self,index:int)->None:
        self.dummy_head = ListNode(index,self.dummy_head.next)
        self.size += 1

    def printList(self)->None:
        current = self.dummy_head
        while current:
            print(current.value,end = "->" if current.next else "")
            current = current.next
        print()

    def swapList(self)->None:
        if self.size <= 1:
            print("元素太少不进行翻转")
            return
        else:
            current_1 = self.dummy_head.next
            current_2 = current_1.next
            current_3 = current_2.next

            self.dummy_head.next = current_2
            current_2.next = current_1
            current_1.next = current_3

            for i in range(1,self.size // 2):
                # 更新指针
                temp = current_1
                current_2 = current_3.next
                current_1 = current_3
                current_3 = current_2.next
                # 交换位置
                temp.next = current_2
                current_2.next = current_1
                current_1.next = current_3

# 开始调用函数
obj = MylinkList()
obj.addAthead(1)
obj.addAthead(10)
obj.addAthead(2)
obj.addAthead(3)
obj.addAthead(21)
obj.addAthead(4)
obj.addAthead(33)
obj.printList()
obj.swapList()
obj.printList()
报错：

AttributeError: 'NoneType' object has no attribute 'next'

这个报错主要是因为在current_3的时候很可能是空的，所以我们需要修改代码，同时还有一些其他的错误，主要是对代码的掌控能力还不够：

代码修正：
    def addAtHead(self,index:int)->None:
        self.dummy_head.next = ListNode(index,self.dummy_head.next)
        self.size += 1

不可以修改头节点

原代码修改后：
class ListNode:
    def __init__(self,data=0,next=None):
        self.value = data
        self.next = next
class MylinkList:
    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def addAtHead(self,index:int)->None:
        self.dummy_head.next = ListNode(index,self.dummy_head.next)
        self.size += 1

    def printList(self)->None:
        current = self.dummy_head
        while current:
            print(current.value,end = "->" if current.next else "")
            current = current.next
        print()

    def swapList(self)->None:
        if self.size <= 1:
            print("元素太少不进行翻转")
            return

        # 使用虚拟头结点简化
        current_1 = self.dummy_head
        current_2 = current_1.next
        current_3 = current_2.next
        while current_1.next!=None and current_1.next.next!=None:
            current_2.next = current_3.next
            current_3.next = current_2
            current_1.next = current_3

            #交换
            current_1 = current_3
            current_2 = current_1.next if current_1 else None
            current_3 = current_2.next if current_2 else None

# 开始调用函数
obj = MylinkList()
obj.addAtHead(1)
obj.addAtHead(10)
obj.addAtHead(2)
obj.addAtHead(3)
obj.addAtHead(21)
obj.addAtHead(4)
obj.addAtHead(33)
obj.printList()
obj.swapList()
obj.printList()
思路2：
代码：
class ListNode:
    def __init__(self,data=0,next=None):
        self.value = data
        self.next = next

class MylinkList:
    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def addAtHead(self,index:int)->None:
        self.dummy_head.next = ListNode(index,self.dummy_head.next)
        self.size += 1

    def printList(self)->None:
        current = self.dummy_head
        while current:
            print(current.value,end = "->" if current.next else "")
            current = current.next
        print()

    def swapList(self)->None:
        if self.size <= 1:
            print("元素太少不进行翻转")
            return

        current = self.dummy_head
        temp_1 = current.next
        temp_2 = temp_1.next
        while current.next and current.next.next:
            temp_1.next = temp_2.next
            temp_2.next = temp_1
            current.next = temp_2

            current = temp_2 if temp_2 else None
            temp_1 = current.next if current else None
            temp_2 = temp_1.next if temp_1 else None

# 开始调用
obj = MylinkList()
obj.addAtHead(1),obj.addAtHead(2),obj.addAtHead(3),obj.addAtHead(10)
obj.addAtHead(15),obj.addAtHead(16),obj.addAtHead(20)
obj.printList()
obj.addAtHead(35)
obj.printList()
obj.swapList()
obj.printList()

链表的倒数第n个节点">删除链表的倒数第N个节点

题目示意：

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

进阶思考：

你能尝试使用一趟扫描实现吗？

链表的题建议大家画图来思考：

针对删除的代码：

def deleteN(self,index:int)->None:
        if index>self.size:
            print("超出了链表的范围")
            return
        else:
            current = self.dummy_head
            for i in range(0,index-1):
                current = current.next
            print(current.next.value)
            current.next =current.next.next
            self.size -= 1

完整的代码：

class ListNode:
    def __init__(self,data=0,next=None):
        self.value = data
        self.next = next

class MylinkList:
    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def addAtHead(self,index:int)->None:
        self.dummy_head.next = ListNode(index,self.dummy_head.next)
        self.size += 1

    def printList(self)->None:
        current = self.dummy_head.next
        while current:
            print(current.value,end = "->" if current.next else "")
            current = current.next
        print()

    def swapList(self)->None:
        if self.size <= 1:
            print("元素太少不进行翻转")
            return

        current = self.dummy_head
        temp_1 = current.next
        temp_2 = temp_1.next
        while current.next and current.next.next:
            temp_1.next = temp_2.next
            temp_2.next = temp_1
            current.next = temp_2

            current = temp_2 if temp_2 else None
            temp_1 = current.next if current else None
            temp_2 = temp_1.next if temp_1 else None

    def deleteN(self,index:int)->None:
        if index>self.size:
            print("超出了链表的范围")
            return
        else:
            current = self.dummy_head
            for i in range(0,index-1):
                current = current.next
            print(current.next.value)
            current.next =current.next.next
            self.size -= 1

# 开始调用
obj = MylinkList()
obj.addAtHead(1),obj.addAtHead(2),obj.addAtHead(3),obj.addAtHead(10)
obj.addAtHead(15),obj.addAtHead(16),obj.addAtHead(20)
obj.printList()
obj.addAtHead(35)
obj.printList()
obj.swapList()
obj.printList()
obj.deleteN(4)
obj.printList()

链表相交">链表相交

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

此题暂时留作思考题，希望大家都思考思考


http://www.niftyadmin.cn/n/5863564.html

相关文章

使用docker开发镜像编译

使用docker开发镜像编译

前言 搭建参考的是官网文档 环境 wsl2 wsl2内存分配和禁用swap 在window主机中，按下快捷键win+r，输入%UserProfile%，会跳转到用户目录，在该目录下，如果没有wsl配置文件，则创建一个.wslconfig，文件类型应为WSLCONFIG，而不是文档类型 我是用vscode来创建的，进入到.wslco…
阅读更多...
Spring Boot定时任务原理

Spring Boot定时任务原理

Spring Boot定时任务原理 在现代应用中&#xff0c;定时任务的调度是实现周期性操作的关键机制。Spring Boot 提供了强大的定时任务支持&#xff0c;通过注解驱动的方式&#xff0c;开发者可以轻松地为方法添加定时任务功能。本文将深入探讨 Spring Boot 中定时任务的实现原理…
阅读更多...
将产品照片（form.productPhotos）转为 JSON 字符串发送给后端

将产品照片（form.productPhotos）转为 JSON 字符串发送给后端

文章目录 1. 前端 form.productPhotos 的当前处理a. 组件绑定b. 当前发送逻辑 2. 如何将 form.productPhotos 转为 JSON 字符串发送给后端a. 修改前端 save() 方法b. 确保 esave API 支持接收字符串 基于你提供的 identify-form.vue 代码&#xff0c;我将分析如何将产品照片&a…
阅读更多...
模块化设计的力量：从「乐高积木」看组合式开发如何降低软件工程风险

模块化设计的力量：从「乐高积木」看组合式开发如何降低软件工程风险

引言&#xff1a;当汽车工厂开始制造积木 想象一家汽车工厂&#xff0c;如果每生产一辆新车都需要重新设计螺丝、焊接发动机、调试轮胎&#xff0c;生产效率将极其低下。但现实中&#xff0c;所有车企都采用「模块化生产」——发动机、变速箱、底盘等核心部件独立开发&#xf…
阅读更多...
学习PostgreSQL专家认证

学习PostgreSQL专家认证

认证途径&#xff1a;由 PostgreSQL 联盟分会授权机构提供的认证考试&#xff0c;出的相关认证。这些认证考试通常具有较高的权威性和认可度&#xff0c;能够证明考生在 PostgreSQL 领域的专业能力。 厂商认证&#xff1a;一些数据库厂商或培训机构也会提供自己的 PostgreSQL 认…
阅读更多...
经验分享—WEB渗透测试中遇到加密内容的数据包该如何测试！

经验分享—WEB渗透测试中遇到加密内容的数据包该如何测试！

经验分享—WEB渗透测试中遇到加密内容的数据包该如何测试&#xff01; 01 加解密的意义 现阶段的渗透测试让我发现越来越多的系统不只是在漏洞修补方面做了功夫&#xff0c;还对一些参数进行加密&#xff0c;干扰爬虫或者渗透测试的进行。 在我小白阶段看到下图这种加密方式…
阅读更多...
容器和虚拟机选择对比

容器和虚拟机选择对比

1. 概述 如果主要需求是学习和测试 Ubuntu 下的命令行工具或服务型应用&#xff0c;推荐使用 Docker Docker 更轻量、更高效&#xff0c;适合快速搭建和销毁环境。 启用 WSL 2&#xff0c;Docker Desktop 是一个非常好的选择。 如果需要完整的桌面环境或进行复杂的系统级开…
阅读更多...
基于SpringBoot实现的宠物领养系统平台功能七

基于SpringBoot实现的宠物领养系统平台功能七

一、前言介绍&#xff1a; 1.1 项目摘要 宠物领养需求增加&#xff1a;随着人们生活水平的提高和对宠物养护意识的增强&#xff0c;越来越多的人选择领养宠物作为家庭的一员。这导致了宠物领养需求的显著增加。 传统领养方式存在问题&#xff1a;传统的宠物领养方式&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023