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

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【不三不四的脑洞】记录一次 “街头搭讪” 之对旋转链表算法的感悟 -> 正文阅读

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

单身越久越难脱单

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

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

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

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

而一旦陷入以上的恶性循环，脱单可不就越来越难了吗？
在这里插入图片描述
所以我决定今天下定决心打破这个循环，那就先从 身材管理（健身减肥）开始！

网上有句话说的很好 —— 一个连自己身体都无法掌控的人，如何掌控人生！

一个人的身材，25岁前，是爹妈给的；25岁之后，是自己修的。

能管好自己身材的人，往往能管理好自己的生活和工作。反之，臃肿的身材背后，可能是一团乱糟糟的生活。

肥胖，给工作带来影响，生活质量也大打折扣，还谈什么奋斗拼搏呢？

在这里插入图片描述

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

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

在这里插入图片描述

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

在这里插入图片描述

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

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

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

在这里插入图片描述

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

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

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

在这里插入图片描述

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

在这里插入图片描述

算法感悟

不过没关系，我又通过这次惨痛的失败，悟出了关于算法的道理 —— 我所身处的 恶性循环 不就很类似
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;
  }
};