直接讲清楚反转链表和判断子链表是怎么搞的【python】
Reversed_sub
反向子链表题,直接把反向链表和子链表讲清楚。
反向
假设有一个链表:1 -> 2 -> 3 -> 4 -> None
-
初始化三个指针:
- prev:用于指向当前节点的前一个节点。初始时 prev 为 None。
- current:用于指向当前节点。初始时 current 指向链表的头节点。
- next:用于保存当前节点的下一个节点,防止在修改 current.next 值之后丢失对下一个节点的引用。
-
进入循环,每次迭代执行以下步骤,直到 current 指向 None(到达链表尾部):
- 将 current.next 指针指向 prev,即将当前节点的下一个节点指向它的前一个节点,完成反转。
- 将 prev 指针指向 current,即将 prev 移动到当前节点的位置。
- 将 current 指针指向 next,即将 current 移动到下一个节点的位置。
- 将 next 指针指向 current 的下一个节点,以便在下一次迭代中使用。
循环迭代过程中的具体步骤如下:
- 第一次迭代:
- prev = None
- current = 1,next = 2
- 将 current.next 指向 prev,即 1 -> None
- prev = 1,current = 2,next = 3
- 第二次迭代:
- prev = 1
- current = 2,next = 3
- 将 current.next 指向 prev,即 2 -> 1
- prev = 2,current = 3,next = 4
- 第三次迭代:
- prev = 2
- current = 3,next = 4
- 将 current.next 指向 prev,即 3 -> 2
- prev = 3,current = 4,next = None
- 第四次迭代:
- prev = 3
- current = 4,next = None
- 将 current.next 指向 prev,即 4 -> 3
- prev = 4,current = None,next = None
-
循环结束后,prev 指针指向反转链表的头节点,即链表的尾部节点。因此,返回 prev。
最终,链表被反转为:4 -> 3 -> 2 -> 1 -> None
求子链表
假设有两个链表: 主链表:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None 子链表:2 -> 3 -> 4 -> None
以下是判断子链表是否为主链表的子链表的每一步骤:
- 初始化两个指针:
- 主链表指针 main_ptr:用于遍历主链表。初始时指向主链表的头节点 1。
- 子链表指针 sub_ptr:用于遍历子链表。初始时指向子链表的头节点 2。
- 进入循环,每次迭代执行以下步骤,直到子链表遍历完毕或找到不匹配的节点:
- 比较当前主链表指针和子链表指针所指向的节点的值。
- 当前主链表指针指向节点 1,子链表指针指向节点 2。它们的节点值不同,因此进入下一步。
- 根据循环结束的情况得出结论:
- 子链表遍历完毕:如果子链表指针为空(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
以下是每一行代码的详细解释:
p1 = a
:初始化指针 p1,指向链表 A 的头节点。while p1:
:进入循环,循环条件为 p1 不为空(即链表 A 遍历未结束)。if p1.val == reversed_b.val:
:判断当前 p1 所指节点的值是否等于反转后的链表 B 的头节点的值。如果不相等,则说明当前节点不可能是相交节点,跳过下面的判断过程,继续遍历链表 A。p2 = p1
:将指针 p2 指向当前 p1 所指节点,作为链表 A 中可能的相交节点。p2_reversed = reversed_b
:将指针 p2_reversed 指向反转后的链表 B 的头节点,用于与 p2 一起遍历两个链表,比较节点值是否相等。while p2 and p2_reversed:
:进入内部循环,循环条件为 p2 和 p2_reversed 都不为空(即两个链表均未遍历结束)。if p2.val != p2_reversed.val:
:比较 p2 和 p2_reversed 所指节点的值是否相等。如果不相等,则说明两个链表在当前节点不相交,跳出循环,继续遍历链表 A。p2 = p2.next
:将 p2 指针向后移动一位,继续遍历链表 A。p2_reversed = p2_reversed.next
:将 p2_reversed 指针向后移动一位,继续遍历反转后的链表 B。if p2_reversed is None:
:判断是否已经遍历完反转后的链表 B,即 p2_reversed 是否为空。如果为空,则说明两个链表在当前节点相交,返回 True。p1 = p1.next
:将 p1 指针向后移动一位,继续遍历链表 A。综上所述,这段代码的作用是通过遍历链表 A 和反转后的链表 B,寻找它们的相交节点。如果找到了相交节点,则返回 True;否则返回 False。
需要注意的是,该算法的时间复杂度为 O(m+n),其中 m 和 n 分别表示链表 A 和链表 B 的长度。
本文来自博客园,作者:ivanlee717,转载请注明原文链接:https://www.cnblogs.com/ivanlee717/p/17852680.html