LeetCode 刷题记录

值得记录的算法题。

链表

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

错误示例

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'

这是因为，在调用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()返回的仍然是一个空值！

方法 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. 反转链表

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

方法 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

迭代只需要记忆pre和cur，内存消耗较小。

评论