ARTS-4

ARTS是由左耳朵耗子陈皓在极客时间专栏《左耳听风》中发起的一个每周学习打卡计划。

Algorithm：至少做一个 LeetCode 的算法题。主要为了编程训练和学习。

Review ：阅读并点评至少一篇英文技术文章。主要为了学习英文，如果你英文不行，很难成为技术高手。

Tip：学习至少一个技术技巧。主要是为了总结和归纳你日常工作中所遇到的知识点。

Share：分享一篇有观点和思考的技术文章。主要为了输出你的影响力，能够输出你的价值观。

Algorithm(算法)

反转单链表

方法一：迭代

假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

复杂度分析

• 时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
• 空间复杂度：O(1)。

方法二：递归

视频地址: https://www.youtube.com/watch?v=lnAhayckbqo

递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？

假设列表为：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

复杂度分析

• 时间复杂度：O(n)，假设 nn 是列表的长度，那么时间复杂度为 O(n)。
• 空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。

分析：

1. 感觉官方题解的递归确实有点难理解，将每一行的的执行结果都打印出来我才看出来到底做了什么操作。

   • 优点：相当于将原链表中的节点从后向前一个一个拆下来并按顺序放入新链表，原链表从后往前每拆一个节点，新链表p的尾部就加上这个被拆下的节点。
   • 缺点：
     1. 没有尾递归优化，链表节点数量大递归很深的情况下存在溢出危险
     2. 方法直接修改内存地址的指向，操作不直观。思路很好，但代码可读性较差（可能我太菜所以一下看不出来）

2. 具体步骤分析：

   1. const p = reverseList(head.next);这一行代码中的p对于整个递归栈而言最终返回了原链表中最后一个节点的地址，也是反转后新链表的head

   2. head.next.next = head;
      

      这一行做的操作比较复杂。

      1. 递归每次退栈后时head相当于从后往前迭代原链表的每一个节点
      2. 实际上head.next已经是原链表的当前尾节点了，在递归上一次退栈过程中的head.next = null;已经将当前递归栈中head.next.next变为null。
      3. 同时head.next即原链表的当前尾节点和新链表p的尾节点是指向同一个内存地址的，也就是新旧链表的尾部此时在内存中是同一个地址。
      4. 看出来以上三点之后，可以得到head.next.next = head;同时也是p[尾节点].next = head，就是将当前节点head的地址添加到新链表p的尾部。这个操作将原链表的第n个节点放到了第n+1个节点的后面，所以仍然存在一点问题，就是循环引用。

   3. head.next = null;因为上一行执行完后实际上使 head.next 和 head.next.next 变成了循环引用，所以需要将这个循环给释放掉，不然新链表的尾部也是一个存在相同的循环引用。因为此时的 head.next === p[在循环引用之前的末尾节点] (同时 head === p[在循环引用之前的末尾节点].next)，即 head.next 和 p[在循环引用之前的末尾节点] 是指向同一个内存地址。所以这一行的操作就是在切断循环引用，切完之后实际上已经实现了当前末位节点的反转

   4. return p;每次递归退栈返回尾部添加了一个新节点的反转后链表

参考文章:

递归与迭代

Review(点评)

1. 对自己诚实: 真正想要的是什么。
2. 始终如一地设计并过上理想的一天: 设计你的日常生活，这样你就可以将所有时间（如果不是大部分）花在你真正重视和关心的事情上。
3. 不要迷失在“成功”的迷宫中，目标不是目的，达到目标后，树立下个目标。

为什么大多数人永远不会得到他们想要的

实现梦想的第一步：诚实守信

尽管人们欺骗别人，但我们对自己说谎最多。我们每天都骗自己。

诚实是情绪化的 - 这就是我们撒谎的原因。我们躲避情绪。我们不想变得脆弱。我们不想被拒绝。我们不想失败。我们不想错。相反，我们把我们的情绪压低并忽视它们 - 这是我们的危险。

要开始你的情感发展之旅，你必须开始对自己更加诚实。

如果你不追求你真正想要的东西，你永远不会感到成功。

实现梦想的第二步：始终如一地设计并过上理想的一天

一旦你开始诚实地对待自己真正想要的东西，就必须停止拖延。

你必须开始设计你的一天，以配合你的梦想。你过着24小时的生活。24小时如何使用这些决定了你生活中的“成功”。

您需要最大限度地利用您在最高优先级上花费的时间。

实现梦想的第三步：不要迷失在“成功”的迷宫中

目标不是目的。他们是手段。一旦达到目标，就需要另一个目标。目标是自我改善的工具。它们是组织生活以实现梦想的方法。他们永远不应该停止。

每击中一个目标，你的信心就会增强。随着你的信心增加，你的想象力和更大目标的能力也会增加。因此，实现目标不应该结束你的未来，它应该扩展你的未来。

如果你过度依附于击中目标所带来的状态，那么你已经用完了未来，现在已经过去了。

结论

实现自己的梦想并实现“成功”是一项艰难但值得追求的目标。

它始于对自己诚实开始和结束。

这可能很困难，因为我们是社交和情感生物。我们不想让其他人失望。我们不想完全诚实地告诉我们我们是谁或我们想要什么。相反，我们埋葬了我们的情感，过着安静的生活。

不要这样做。

不要自欺欺人。

开始告诉周围的人你真正想要的东西。保留支持你的人。放弃那些试图让你留在原地的人。

然后，设计你的日常生活，这样你就可以将所有时间（如果不是大部分）花在你真正重视和关心的事情上

当你成功时，不要迷路。

如果你不知道自己到底是谁 - 那么成功就会误导你。你要么过度地依附于你所开发的特定状态，要么迷失在其他人的议程（即“机会”）的迷宫中。

一直以来，你需要不断地与自己保持联系，并对自己诚实。老实说，你需要对出现的机会更快地说“不”。

仅仅因为某件事是一个很好的机会并不意味着你应该这样做。一切都有成本。时间是最大的成本。

当你开始对最高的自我完全诚实时，就会立即开始发生惊人的事情。

成功将会发生。必须成功。但它只有在你开始过你想要的生活时才会发生，而不是在成功的时候迷失。

Tip(技巧)

使用Jenkins Theme美化jenkins

Jenkins-Theme生成jenkins定制主题

Share(分享)

使用Flasgger让Python集成Swagger(翻译)

打赏