【左程云算法全讲6】链表相关

系列综述：
💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于左程云算法课程进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈【C++】秋招&实习面经汇总篇

---

---

😊点此到文末惊喜↩︎

链表问题

基本问题

1. 笔试和面试
   • 对于笔试，一般不需要在意空间复杂度
   • 对于面试，时间复杂度作为第一位，但是一定要尽量节省空间
2. 题目
   • 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
   • 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
   • 输入链表头节点，奇数长度返回中点的前一个，偶数长度返回上中点的前一个
   • 输入链表头节点，奇数长度返回中点的前一个，偶数长度返回下中点的前一个

// 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
Node FindNode(Node head) {// 健壮性检查if (head == nullptr || head->next == nullptr || head->next->next == nullptr)return head;// 初始化Node slow = head->next;Node fast = head->next->next;while (fast->next != nullptr && fast->next->next != nullptr) {slow = slwo->next;fast = fast->next;}return slow;
}// 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
Node FindNode(Node head) {// 健壮性检查if (head == nullptr || head->next == nullptr || head->next->next == nullptr)return head;// 初始化Node slow = head->next;Node fast = head->next;		// 初始化位置不同while (fast->next != nullptr && fast->next->next != nullptr) {slow = slwo->next;fast = fast->next;}return slow;
}

3. 判断是否为链表是否回文
   • 思路1：先使用栈进行存储，然后再从链表头开始与栈中元素进行比较
   • 思路2：找到链表中间，然后使用栈存储后半部分，再链表与栈中进行一一比较
   • 思路3：原地空间，找到链表中间，将后半部分指针逆序，然后

// 定义三个匿名函数进行处理
auto 找中点
auto 反转链表
auto 比较

4. 链表调整：小于放左边，等于放中间，大于放右边
   • 笔试使用：放在数组中，然后进行partition
   • 桶思想：进行区域划分：小于、等于、大于的每个区域有两个指针

在这里插入代码片

5. 克隆带有随机指针的链表
   • 思路1：使用unordered_map<int, Node*>，遍历链表存入哈希表中，再遍历一遍设置随机指针
   • 思路2：在每个节点后面克隆并插入，然后设置新插入节点的random指针，分离新节点链表（这个过程和random无关）

Node* copyRandomList(Node* head) {if (head == nullptr) return nullptr;// 复制结点并插入到结点后面Node *cur  = head;Node *next = nullptr;while (cur != nullptr) {next = cur->next;cur->next = new Node(cur->val);cur->next->next = next;cur = next;}// 复制所有结点的random关系cur = head;Node *cur_copy = nullptr;while (cur != nullptr) {next = cur->next->next; // 先记录cur_copy = cur->next;cur_copy->random = cur->random != nullptr ? cur->random->next : nullptr;cur = next;             // 后迭代}// 分离链表Node *res = head->next;cur = head;while (cur != nullptr) {// 先记录，后使用，注意每次迭代要还原和结尾情况next = cur->next->next;cur_copy = cur->next;cur->next = next;cur_copy->next = next != nullptr ? next->next : nullptr;cur = next;}return res;
}

6. 如何两个链表相交返回第一个交点， 如果不相交返回nullptr
   • 思路1：使用unordered_set，一边遍历一边查set表，判断是否成环
   • 思路2：遍历两个链表长度，然后相减。再遍历长链表-短链表长度次，最后共同再一起遍历

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == nullptr || headB == nullptr) return nullptr;ListNode *cur1 = headA;ListNode *cur2 = headB;// 求两个链表长度的差值int n = 0;while (cur1->next != nullptr) {++n;cur1 = cur1->next;} while (cur2->next != nullptr) {--n;cur2 = cur2->next;}// 如果两个链表相交，必然最后一个结点地址相同// 否则两个链表不相交if (cur1 != cur2) return nullptr;cur1 = (n > 0 ? headA : headB);cur2 = (n > 0 ? headB : headA);n = abs(n); // 差值转正// 长链表头先走差值步while (n != 0) {--n;cur1 = cur1->next;}// 两个链表头一起走while (cur1 != cur2) {cur1 = cur1->next;cur2 = cur2->next;}return cur1;
}

7. 链表成环问题：如果成环返回环的入口结点
   • 遍历成环的单链表，如果
   • 思路1：使用unordered_set，一边遍历一边查set表，判断是否成环
   • 思路2：快指针一次走两步，慢指针一次走一步。然后在环内相遇后，然后快指针重新从头开始，快慢指针继续走，再次遇到环的入口

ListNode *detectCycle(ListNode *head) {// 健壮性检查：注意必须都不为空if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return nullptr;// 先进行一次，然后就可以将判断条件设置为fast != slowwListNode *fast = head->next->next;ListNode *slow = head->next;// 快指针走两步，慢指针走一步while (fast != slow) {if (fast->next == nullptr || fast->next->next == nullptr)return nullptr;slow = slow->next;fast = fast->next->next;}// 然后快指针指向头，两个指针同步每次走一步fast = head;while (fast != slow) {slow = slow->next;fast = fast->next;}return slow;
}

8. 知道一个单链表中的某个结点地址，删除该结点
   • 思路1：遍历链表到该结点的前一个结点，然后进行删除
   • 思路2（借尸还魂）：使用该节点的后一个结点的值拷贝覆盖该结点，然后删除该节点的后一个结点。
     • 拷贝开销：如果结点拷贝开销特别大，如集群则无法进行
     • 结尾结点问题：无法删除链表的最后一个结点，但是结尾可以使用一个空结点哨兵，标识结尾

---

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。 不如点赞·收藏·关注一波

---

🚩点此跳转到首行↩︎

参考博客

1. 对数器
2. 单调队列
3. 快速链表quicklist
4. 《深入理解计算机系统》
5. 侯捷C++全系列视频
6. 待定引用
7. 待定引用
8. 待定引用