首页 > 编程语言 >直接讲清楚反转链表和判断子链表是怎么搞的【python】

直接讲清楚反转链表和判断子链表是怎么搞的【python】

时间:2023-11-23 22:33:45浏览次数:42  
标签:p2 current prev python 讲清楚 链表 next 节点

Reversed_sub

反向子链表题,直接把反向链表和子链表讲清楚。

反向

假设有一个链表:1 -> 2 -> 3 -> 4 -> None

  1. 初始化三个指针:

    • prev:用于指向当前节点的前一个节点。初始时 prev 为 None。
    • current:用于指向当前节点。初始时 current 指向链表的头节点。
    • next:用于保存当前节点的下一个节点,防止在修改 current.next 值之后丢失对下一个节点的引用。
  2. 进入循环,每次迭代执行以下步骤,直到 current 指向 None(到达链表尾部):

    • 将 current.next 指针指向 prev,即将当前节点的下一个节点指向它的前一个节点,完成反转。
    • 将 prev 指针指向 current,即将 prev 移动到当前节点的位置。
    • 将 current 指针指向 next,即将 current 移动到下一个节点的位置。
    • 将 next 指针指向 current 的下一个节点,以便在下一次迭代中使用。

    循环迭代过程中的具体步骤如下:

    • 第一次迭代:
      1. prev = None
      2. current = 1,next = 2
      3. 将 current.next 指向 prev,即 1 -> None
      4. prev = 1,current = 2,next = 3
    • 第二次迭代:
      1. prev = 1
      2. current = 2,next = 3
      3. 将 current.next 指向 prev,即 2 -> 1
      4. prev = 2,current = 3,next = 4
    • 第三次迭代:
      1. prev = 2
      2. current = 3,next = 4
      3. 将 current.next 指向 prev,即 3 -> 2
      4. prev = 3,current = 4,next = None
    • 第四次迭代:
      1. prev = 3
      2. current = 4,next = None
      3. 将 current.next 指向 prev,即 4 -> 3
      4. prev = 4,current = None,next = None
  3. 循环结束后,prev 指针指向反转链表的头节点,即链表的尾部节点。因此,返回 prev。

最终,链表被反转为:4 -> 3 -> 2 -> 1 -> None

求子链表

假设有两个链表: 主链表:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None 子链表:2 -> 3 -> 4 -> None

以下是判断子链表是否为主链表的子链表的每一步骤:

  1. 初始化两个指针:
    • 主链表指针 main_ptr:用于遍历主链表。初始时指向主链表的头节点 1。
    • 子链表指针 sub_ptr:用于遍历子链表。初始时指向子链表的头节点 2。
  2. 进入循环,每次迭代执行以下步骤,直到子链表遍历完毕或找到不匹配的节点:
    • 比较当前主链表指针和子链表指针所指向的节点的值。
    • 当前主链表指针指向节点 1,子链表指针指向节点 2。它们的节点值不同,因此进入下一步。
  3. 根据循环结束的情况得出结论:
    • 子链表遍历完毕:如果子链表指针为空(sub_ptr 为 None),则说明子链表已经遍历完毕,即子链表是主链表的子链表。返回 True。
    • 找到不匹配的节点:如果子链表指针不为空(sub_ptr 不为 None),则说明在主链表中找不到与子链表完全匹配的连续节点,即子链表不是主链表的子链表。返回 False。

根据上述过程,可以得出结论:子链表 2 -> 3 -> 4 不是主链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 的子链表。

class Solution:
    def isReverseChild(self, a, b) :
        reversed_b = self.reverse_linked_list(b)  # 反转链表 B
        p1 = a
        while p1:
            if p1.val == reversed_b.val:
                p2 = p1
                p2_reversed = reversed_b
                while p2 and p2_reversed:
                    if p2.val != p2_reversed.val:
                        break
                    p2 = p2.next
                    p2_reversed = p2_reversed.next
                if p2_reversed is None:
                    return True
            p1 = p1.next
        
        return False


    def reverse_linked_list(self,l):
        prev = None
        current = l
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        return prev
        

以下是每一行代码的详细解释:

  1. p1 = a:初始化指针 p1,指向链表 A 的头节点。
  2. while p1::进入循环,循环条件为 p1 不为空(即链表 A 遍历未结束)。
  3. if p1.val == reversed_b.val::判断当前 p1 所指节点的值是否等于反转后的链表 B 的头节点的值。如果不相等,则说明当前节点不可能是相交节点,跳过下面的判断过程,继续遍历链表 A。
  4. p2 = p1:将指针 p2 指向当前 p1 所指节点,作为链表 A 中可能的相交节点。
  5. p2_reversed = reversed_b:将指针 p2_reversed 指向反转后的链表 B 的头节点,用于与 p2 一起遍历两个链表,比较节点值是否相等。
  6. while p2 and p2_reversed::进入内部循环,循环条件为 p2 和 p2_reversed 都不为空(即两个链表均未遍历结束)。
  7. if p2.val != p2_reversed.val::比较 p2 和 p2_reversed 所指节点的值是否相等。如果不相等,则说明两个链表在当前节点不相交,跳出循环,继续遍历链表 A。
  8. p2 = p2.next:将 p2 指针向后移动一位,继续遍历链表 A。
  9. p2_reversed = p2_reversed.next:将 p2_reversed 指针向后移动一位,继续遍历反转后的链表 B。
  10. if p2_reversed is None::判断是否已经遍历完反转后的链表 B,即 p2_reversed 是否为空。如果为空,则说明两个链表在当前节点相交,返回 True。
  11. p1 = p1.next:将 p1 指针向后移动一位,继续遍历链表 A。

综上所述,这段代码的作用是通过遍历链表 A 和反转后的链表 B,寻找它们的相交节点。如果找到了相交节点,则返回 True;否则返回 False。

需要注意的是,该算法的时间复杂度为 O(m+n),其中 m 和 n 分别表示链表 A 和链表 B 的长度。

标签:p2,current,prev,python,讲清楚,链表,next,节点
From: https://www.cnblogs.com/ivanlee717/p/17852680.html

相关文章

  • python编程模拟题二
    重要提示:如下四个题都很类似,从简到难不等,请注意:尽管要求输入数字,但如果数字本身在题目中不需要参与计算,那么可以直接把这个数字当字符串来处理即可。如果数字参与计算了,可以把每个数字通过 eval()或 int()转换即可。这四个题目考察大家输入,输出,循环,字符串里每个字符的索引......
  • 简单的用Python采集股票数据,保存表格后分析历史数据
    前言字节跳动如果上市,那么钟老板将成为我国第一个世界首富趁着现在还没上市,咱们提前学习一下用Python分析股票历史数据,抱住粗大腿坐等起飞~好了话不多说,我们直接开始正文准备工作环境使用Python3.10解释器Pycharm编辑器模块使用requests—>数据......
  • pythonChap3变量与函数
    变量与操作变量用=赋值新的值会覆盖掉旧的值新值的数据类型不一定要与旧的相等变量命名规则:必须以字母或下划线(_)开头命名可由字母、数字和下划线组成大小写敏感尽量避免使用保留字命名保留字:['False','None','True','peg_parser','and','as','assert','async......
  • 聪明办法学python chap2数据类型与操作 3变量与函数
    Python(二)数据类型与操作类型print(type(2))#整型intprint(type(2.2))#浮点型floatprint(type(2>3.4))#布尔型boolprint(type(type(2)))#类型typeprint(t......
  • Python中的构造方法
     构造方法在Python中的使用:创建对象时用于初始化对象的实例变量。通过__init__()来定义1、什么是构造方法在面向对象编程中,构造方法是一个特殊的方法,用于在创建对象时初始化对象的状态。它在对象创建的过程中自动调用,负责为对象设置初始值。构造方法通常用于执行与对象相关的......
  • Python中,if __name__=="__main__"学习
    注意:Python的代码执行,都是依次从上往下执行在Python中,每个模块都有一个内置的变量name,用于表示当前模块的名称。当一个Python文件被执行时,Python解释器会首先将该文件作为一个模块导入,并执行其中的代码。此时,__name__的值为模块的名称。ifname==‘main’是一个常见的用法,它......
  • 代码随想训练营第三十九天(Python)| 62.不同路径、63. 不同路径 II、343. 整数拆分
    62.不同路径classSolution:defuniquePaths(self,m:int,n:int)->int:#dp[i][j]代表到达dp[i][j]有多少不同路径dp=[[0]*nfor_inrange(m)]#初始化foriinrange(m):dp[i][0]=1forjinra......
  • 运行python的几种方式
    通过cmd终端去运行按住win+r打开命令提示符,然后输入python,就可以进入python环境,输入你需要指定的python代码即可。#注意:这种方法只是建议临时使用一下,因为午饭保存数据。通过记事本新建一个记事本文档(后缀是否修改为.py不影响)里面输入python代码,一样通过cmd窗口去执行。......
  • 聪明办法学python.
    循环:foriinrange(x,y,z):     [x,y),z为步长,省略第一个参数默认为0,省略第三个参数默认为1.     while条件:     continue跳过此次循环     break跳出当前整个循环     pass占位符,不会被运行字符串:单引号'和双引号"......
  • 代码随想录-链表
    203.移除链表元素https://leetcode.cn/problems/remove-linked-list-elements/description//***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):......