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

这篇具有很好参考价值的文章主要介绍了直接讲清楚反转链表和判断子链表是怎么搞的【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 的下一个节点，以便在下一次迭代中使用。
循环迭代过程中的具体步骤如下：
- 第一次迭代：
  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
循环结束后，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 的长度。文章来源地址https://www.toymoban.com/news/detail-747118.html