跳转至

LeetCode 刷题记录

值得记录的算法题。

链表

剑指 Offer 06. 从尾到头打印链表

image-20221224104339546

错误示例

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

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if head is None:
            result = []
        else:
            result = self.reversePrint(head.next).append(head.val)
        return result

报错:

Text Only
AttributeError: 'NoneType' object has no attribute 'append'

image-20221224104447455

这是因为,在调用append()方法时,数组直接在最后添加了一个元素,返回值是空值。因此不需要将self.reversePrint(head.next).append(head.val)赋值给result了,赋的值也是None

正确写法:

方法 1(递归)

Python
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if head is None:
            return []
        else:
            return self.reversePrint(head.next) + [head.val]

这里没有使用append()方法,而是用+来连接两个数组。

如果使用append()方法,则仍会报错,因为append()返回的仍然是一个空值!

image-20221224110338322

方法 2(将链表的元素逐个输入到新数组中,再逆向排序)

Python
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        result = []
        while head is not None:
            result.append(head.val)
            head = head.next
        return result[::-1]

这种方法使用append(),将链表的元素逐个输入到新数组中,再逆向排序。

剑指 Offer 24. 反转链表

image-20221224130541479

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 若输入本身就是 None,则直接输出 head(测试用例中,可能会直接输入一个 None,因此需要判断这种情况)
        if head is None:
            return head
        # 若递归到了最后,head.next 为 None,则返回 head,即返回 5
        if head.next is None:
            return head
        # 递归
        result = self.reverseList(head.next)
        # 目前 head 是 4,需要将 5.next 改成 4,而 5 就是 4.next,所以需要将 4.next.next 改成 4
        head.next.next = head
        # 目前 4.next 还是 5,也就是 5 -> 4 -> 5。需要将 4.next 改成 None,形成 5 -> 4 -> None
        head.next = None
        # 返回 5 -> 4 -> None
        return result

方法 1:递归

核心就是理解两行代码:

Python
head.next.next = head
head.next = None

参考讲解:

https://zhuanlan.zhihu.com/p/60117407

image-20221224130703661

方法 2:迭代

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        pre = None
        # 当 cur 不是 None 时
        while cur:
            # 暂存 cur.next,因为马上要修改 cur.next
            tmp = cur.next
            # 修改 cur.next 为 pre,实现反转
            cur.next = pre
            # 准备下一轮迭代
            pre = cur
            cur = tmp
        return pre

image-20221224132549955

image-20221224132558846

迭代只需要记忆precur,内存消耗较小。

评论