RT-Thread-提高你的代码水平上限 | 刷题日记2RT-Thread问答社区

提高你的代码水平上限 | 刷题日记2

发布于 2021-07-06 01:15:13 浏览：982 订阅该版

[tocm]

July 6, 2021 @Author：lebhoryi@gmail.com      @Language: Python

> “真正的大师永远怀着一颗学徒的心”

> ”要走出自己的舒适区“

> ”一定要自己独立完成，那怕写的再烂“

Leetcode 206：[https://leetcode-cn.com/problems/two-sum](https://leetcode-cn.com/problems/reverse-linked-list/)

![image.png](https://oss-club.rt-thread.org/uploads/20210706/a7347fb0a4f3e600cbc938816e8ee4f2.png.webp)

反转链表。

开始撸这道题目的先决条件是：晓得链表是个啥玩意儿

科班出身的懂得都懂。但是我不是。这还是我后来恶补的知识。

”大把的时间让我学我没学，到了不该学的年纪拼命学“

除了上面一个知识点以外，对于 Python 写手来说，压根就没有链表这个数据结构。

咋办？

自己创建一个。

很巧妙的用了类方法，创建了类的节点的定义:

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def __repr__(self):
        return str(self.val)
```

并且上述方法都是默认写法，至少我没有见到过第二种，如果有，请评论留言或者私密我一下。

有了节点，还需要将列表转成节点：(此处借鉴了 leetcode 中的代码部分)

```python
def string2ListNode(array):
    # 创建首节点
    dummy_root = ListNode(0)
    ptr = dummy_root
    for elem in array:
        ptr.next = ListNode(elem)
        ptr = ptr.next

return dummy_root.next
```

好了，列表创建完成，但是，怎么检验列表创建成功？

`print` 大法好

```python
def link_print(node):
    if not node.val:
        return None

while node:
        yield node.val
        node = node.next
```

完整的创建到输出：

```python
def main():
    head = [1, 2, 3, 5, 4]
    head = string2ListNode(head)
    for node in link_print(head):
        print(node, end=" ")
```

别问为啥会出现 `yield`，`python` 开发者这个技巧哪能好意思叫做 `python` 开发...

还有就是上面类别中出现的 `__repr__`，目的是为了调试的时候，直接看到 `node`，而不用 `print(node.val)` 来查看，也可以不用，但是我习惯了用

更多的关于 `python` 和链表相爱相杀的代码：[https://github.com/Lebhoryi/Algorithms/tree/master/2.线性表](https://github.com/Lebhoryi/Algorithms/tree/master/2.%E7%BA%BF%E6%80%A7%E8%A1%A8)

文章：[https://blog.csdn.net/weixin_37598106/article/details/102224569](https://blog.csdn.net/weixin_37598106/article/details/102224569)

---

再回到题目中来，题目是反转链表，在对于链表的算法题来说是非常的基础，

同时也是非常的友好，对于初学者。

该题目也被纳入《剑指offer》中。

有以下两种解法：

1. 利用 `python` 的特性，将链表转换成列表，然后列表反转，再转换成链表

> 本文未实现，上面的 github 链接中有实现

2. 创建一个临时节点，将当前节点指向临时节点，临时节点更改为当前节点，然后当前节点往前移。

第二种的实现方式有**循环和递归**两种。

其中递归仅是拓展思维用，在内存和计算速度上均是循环更优。

这里介绍的是第二种解决方法：

```python
def fun1(head: ListNode) -> ListNode:
    # 当前节点指向上一个节点
    if not head or not head.next:
        return head

ptr = None
    while head:
        tmp = head.next
        head.next = ptr
        ptr = head
        head = tmp
    return ptr

def fun2(head: ListNode) -> ListNode:
    # 不算太优化的优化，省略tmp，python独有
    if not head or not head.next:
        return head

ptr = None
    while head:
        head.next, ptr, head = ptr, head, head.next
    return ptr

def fun3(head: ListNode, ptr=None) -> ListNode:
    # 扩展思维：递归，凡是能够循环的都能够写成递归
    # 此解法为尾递归，即直接以递归返回值作为结果，一般编译器会做优化，避免多余的函数开栈操作，实现效果相当于迭代
    if head:
        head.next, ptr, head = ptr, head, head.next

return fun3(head, ptr) if head else ptr
```

科普一下 `python` 的优美之处，推荐掌握：

```python
# a、b 互相交换
tmp = a
a = b
b = a

# 可以写成
a, b = b, a
```