【不三不四的脑洞】记录一次 “街头搭讪” 之对旋转链表算法的感悟

ShaderJoy 的不三不四脑洞

单身越久越难脱单

前一阵子在网上看到一句话 —— 单身越久越难脱单

作为大龄单身程序猿的我深以为然,甚至觉得单身的时间久了,真的会丧失和异性相处的能力。

以我个人的生活感受(当然不能代表其他所有人单身都是这个原因)来说,恶性循环 主要包含以下点

单身 -> 宅家不爱出门 -> 奶茶甜品不离手,身材走样 -> 缺乏运动和面对面社交 -> 圈子变小、逐渐社恐 -> 单身

而一旦陷入以上的恶性循环,脱单可不就越来越难了吗?

image.png

所以我决定今天下定决心 打破 这个循环,那就先从 身材管理(健身减肥) 开始!

网上有句话说的很好 —— 一个连自己身体都无法掌控的人,如何掌控人生
一个人的身材,25岁前,是爹妈给的;25岁之后,是自己修的。
能管好自己身材的人,往往能管理好自己的生活和工作。反之,臃肿的身材背后,可能是一团乱糟糟的生活。
肥胖,给工作带来影响,生活质量也大打折扣,还谈什么奋斗拼搏呢?

image.png

下定决心后,立刻用吃奶的力气做了两下卧推。。。哎呀妈呀,太累了!

点杯 奶茶 补充补充能量吧~ 有能量才有力气锻炼 ~

image.png

但是毕竟我不是个 没羞没臊 的人,因为喝了奶茶,心里还是有一丢丢 愧疚感 的,所以打算出门溜达溜达。顺便缓解一下自己社恐的症状,暂时脱离虚拟的二次元生活,尝试融入一下现实社会。当我正在街上漫不经心的向前走着时,突然迎面走来一个妹子,朱唇玉面,头发梳个丸子头,身穿碎花裙子,曼妙身材呼之欲出

image.png

我远远看去,感觉妹子仿佛在和我微笑,但是当妹子越走越近,社恐又羞涩的我没敢和她对视,而是选择低头默默地继续往前走。但是走着走着,脑中一个声音狠狠地训斥我:“ShaderJoy,你出门不就是为了打破恶性循环的吗?既然上天都给你安排了这样的一个千载难逢的机会,你都不选择把握,你都这么大年龄了,还怕个什么鸡毛?就算被拒绝身上能掉块肉吗?

言之有理啊!这个心灵的声音

image.png

我重新鼓起了勇气,稍稍加快了脚步往回走寻觅妹子的踪影。可是走了一会,却再没看到妹子的身影,我顿时感到有些失望,后悔当时自己没有好好把握机会,果然世上没有后悔药。。。

image.png

正在我内心懊恼的时候,好巧不巧的,妹子居然出现在我前方不远处,原来她也在往回走!难道她也是来找我的吗?!天呐,难道我这个大龄单身猿今天终于要逆天走 “狗屎运” 。。。啊呸,“桃花运” 了嘛!~

我整理了一下衣服,当妹子走到我跟前的时候,我仿佛看见了她又微微冲我一笑,此时我决心一定要把握住这次机会上前和她搭讪了,刚说:“你好……”。

谁知 “好” 字还没说出口,妹子就惊恐地 “咻” 得一下以光速 “弹开” 了,脸上还满是嫌弃的表情,躲得远远的,然后迅速消失,留我一人尬在原地,原来上面的那一切都是我的幻觉。。。她压根没有对我微笑,哪有什么狗血纯爱偶像剧的上天安排。。。

image.png

随着我这次的搭讪失败,我又回到了上面的 “恶性循环” 圈子里。。。

image.png

算法感悟

不过没关系,我又通过这次惨痛的失败,悟出了关于算法的道理 —— 我所身处的 恶性循环 不就很类似

LeetCode 61 Rotate List (旋转链表) 嘛,命运之轮一直在周而复始的循环旋转。。。

好了,为了简单起见举个例子,原链表如下,

l = 5

1->2->3->4->5->nullptr

k = 2 的情况下

4->5->1->2->3->nullptr


///@note 代码原作者: Huahua

///      详细注释:ShaderJoy

class Solution {

public:

  ListNode* rotateRight(ListNode* head, int k) {

    if (!head) return head;   

    int l = 1;                                    ///< 记录链表的长度,默认为 1

    ListNode* tail = head;                        ///< 尾指针,初始化指向链表头部

    while (tail->next) { tail = tail->next; ++l; } ///< 遍历链表,记录链表的长度,同时尾指针指向链表尾部

    k %= l; ///< 由于是循环链表,所以需要排除结果重复的步数,得到实际的旋转次数

    if (k == 0) return head; ///< 无需循环

    /// @note ★

    ListNode* prev = head;            ///< 作用:指向要操作结点的前一个结点。初始为链表头部

    while (--l > k) prev = prev->next; ///< prev 向后移动 l-k-1 步            【例子中的 3】

    ListNode* new_head = prev->next;  ///< 然后保存 prev 后面的结点作为新头 【例子中的 3 所指的下一个,是 4】

    tail->next = head;                ///< 将旧头链接到链表尾部            【例子中的 1】

    prev->next = nullptr;              ///< 处理新尾部                      【例子中的 3 所指的下一个,断开 4】

    return new_head;

  }

};

其中为了加深记忆,再次将 关键步骤 ★ 总结如下

1. 将 prev 移动到待操作(新头)结点的前一个结点;

2. 保存待操作结点为 new_head

3. 将 head 链接到链表尾端;

4. 断开 prev 和原先其下一个(即新头)结点的链接

结尾

好了,算法挺简单的,几句话就介绍完了,我要去默默疗伤了(希望我的惨痛经历能够让大家对这个算法题目和代码有深刻印象,那也就值了

image.png
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 考察链表的题目不会要求我们时间复杂度,因为链表并不像是数组那样,可以方便的使用各种排序算法和查找算法。因为链表涉及...
    熊大状阅读 648评论 0 1
  • 题目 输入一个链表,输出该链表中倒数第k个节点。 为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第...
    Longshihua阅读 291评论 0 2
  • 上篇文章介绍了数组,哈希表,字符串相关的算法,这篇文章介绍另一个重要的数据结构,链表 链表特点 链表,和数组相比较...
    bigonelby阅读 296评论 0 0
  • 1. 前言 上次写Python操作LevelDB时提到过,有机会要实现下SkipList。摘录下wiki介绍: 跳...
    kophy阅读 15,797评论 3 33
  • 本来以为一篇就能写完的,后来又感觉一篇多了一些,所以关于链表的简单算法题有加了个续篇,和上一篇一样,难度不会太大。...
    zero_sr阅读 565评论 0 4