系列综述:
💞目的:本系列是个人整理为了秋招面试coding
部分的,整理期间苛求每个算法题目,平衡可读性
与代码性能
(leetcode运行复杂度均打败80%以上)。
🥰来源:材料主要源于【CodeTopHot200】进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证,所有代码均优先参考最佳性能。
🤭结语:如果有帮到你的地方,就点个赞和关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇
文章目录
- 基础知识
- 链表定义
- 链表基本操作
- 常见题目
- 206. 反转链表
- 25. K 个一组翻转链表
- 21. 合并两个有序链表
- 交换相邻链表节点
- 141. 环形链表
- 求环形链表的入口
- 92. 反转链表 II
- 160. 相交链表
- 23. 合并K个排序链表
- 143. 重排链表
- 142. 环形链表 II
- 19. 删除链表的倒数第 N 个结点
- 移除链表中的重复结点
- 删除无序链表中值重复出现的节点
- 参考博客
😊点此到文末惊喜↩︎
基础知识
链表定义
struct ListNode {
int val;
ListNode *next;
ListNode(int v) : val(v), next(nullptr){}
};
// 简化定义:在 C++ 中定义struct,可以省略struct并直接使用结构体名称。
ListNode *vhead = new ListNode(-1);
链表基本操作
- 删除指定链表节点
虚拟头节点的定义
:为了统一节点的遍历操作,避免无头节点的释放错误虚拟头节点的释放
:C++不支持GC内存自动清理,所以需要手动释放,避免内存泄漏
ListNode* removeElements(ListNode* head, int val) {
// 1. 定义头节点
ListNode *vHead = new ListNode(0, head);
// 2. 逻辑处理部分
ListNode* cur = vHead; // 定义工作指针cur
while(cur->next != nullptr){
if(cur->next->val == val){ // 为了获取操作节点的前一个节点进行删除
ListNode* tmp = cur->next; // key:结点删除后要释放
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next; // 工作指针++
}
}
// 3. 释放头节点
head = vHead->next; // key:解决头节点是目标值的情况
delete(vHead); // 不要忘记啦
return head;
}
- 反转链表
- 链表的遍历
- 遍历使用当前结点:while (cur != nullptr) { }
- 遍历使用当前结点的前一个结点:while (cur->next != nulllptr) { }
// 反转链表:链表前一个元素需要重新修改next指针 ListNode* reverseList(ListNode* head) { // 初始化:注意prve指向空 ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { // TODO: cur执行结束节点时停止 // 先记录后使用:注意记录的是cur->next ListNode* tmp = cur->next; cur->next = pre; // 迭代:pre和cur节点都前进一位 pre = cur; cur = tmp; } return pre; }
- 链表的遍历
- 链表求中心
// 中心结点(偶数返回右结点) ListNode* middleNode(ListNode* head) { ListNode *slow = head; ListNode *fast = head; while (fast != nullptr && fast->next!= nullptr) { slow = slow->next; fast = fast->next->next; } cout << slow->val; return slow; } // 中心结点(偶数返回左结点) ListNode* middleNode(ListNode* head) { ListNode *slow = head; ListNode *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } return slow; }
常见题目
206. 反转链表
ListNode* reverseList(ListNode* head) {
ListNode *vhead = new ListNode(-1, nullptr);
while (head != nullptr) {
ListNode *tmp = head;
head = head->next;
tmp->next = vhead->next;
vhead->next = tmp;
}
ListNode *p = vhead->next;
delete vhead;
return p;
}
25. K 个一组翻转链表
未完待续。。。
21. 合并两个有序链表
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 健壮性检查
// 虚拟头节点和尾指针
ListNode *vhead = new ListNode(-1);
ListNode *tail = vhead;
// 算法部分
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next; // key: 忘记了
}
// 收尾
tail->next = list1 == nullptr ? list2 : list1;
// 防止内存泄漏
ListNode *p = vhead->next;
vhead->next = nullptr;
delete vhead;
return p;
}
交换相邻链表节点
- letcode题目网址
ListNode* swapPairs(ListNode* head){ // 健壮性检查 if(head == nullptr) return nullptr; // 指向操作节点组的第一个和第二个 ListNode* prior_first; ListNode* prior_second;- // 增加虚拟头节点 ListNode* vHead = new ListNode(0); vHead->next = head; ListNode *cur = vHead; while(cur->next != nullptr && cur->next->next != nullptr){ prior_first = cur->next; prior_second = cur->next->next; prior_first->next = prior_second->next; prior_second->next = prior_first; cur->next = prior_second; cur = prior_second->next;// cur指向被操作节点组的前一个 } return vHead->next; }
141. 环形链表
- 题目
- 给你一个链表的头节点 head ,判断链表中是否有环。
- 思路
- 哈希缓存:每遍历一个元素,先查询哈希表中是否存在该元素的指针,若不存在则将该元素加入到哈希表中
- 双倍指针:快指针一次走两步,慢指针一次走一步,只要有环,最终一定会相遇
// 不进行第一次操作的初始化 bool hasCycle(ListNode *head) { ListNode* fast = head, *slow = head; while (true) { // 迭代:先探测后迭代 if (fast == nullptr || fast->next == nullptr) return false; fast = fast->next->next; slow = slow->next; // TODO // 判断结束条件 if (fast == slow) break; } return true; } // 进行第一次运行的初始化 bool hasCycle(ListNode *head) { // 初始化第一次运行结果 if (head == nullptr || head->next == nullptr) return false; ListNode *slow = head; ListNode *fast = head->next->next; // 算法部分 while (fast != slow) { if (fast != nullptr && fast->next != nullptr) { fast = fast->next->next; }else { return false; } slow = slow->next; } return true; }
求环形链表的入口
- letcode题目链接
- 一个节点的next是否能访问,需要判断该节点是否存在
- 只写容易判断的逻辑,其他的交给else
ListNode *detectCycle(ListNode *head) {
ListNode* slow=head;
ListNode* fast=head;
// 1. 快指针走两步,慢指针走一步
while(fast!=NULL&&fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
// 如果相等,让慢指针从头开始走,快慢指针一起移动,相等则为链表环形入口
if(slow==fast){
slow=head;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return fast;
}
}
return NULL;
}
92. 反转链表 II
- 题目
- 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回反转后的链表 。
ListNode* reverseBetween(ListNode* head, int l, int r) {
// 逆序两个指针间的部分
auto reverse_list = [](ListNode *head, ListNode *tail){
ListNode *p = nullptr;
while (head != tail) {
p = head;
head = head->next;
p->next = tail->next;
tail->next = p;
}
};
ListNode *vhead = new ListNode(-1, head);
// 获取需要进行处理的区间的头尾指针
ListNode *left = vhead;
for (int i = 0; i < l; ++i) {
left = left->next;
}
ListNode *right = vhead;
for (int i = 0; i < r; ++i) {
right = right->next;
}
// 获取逆序区间的前指针prev和后指针behind
ListNode *prev = vhead;
while (prev->next != left) prev = prev->next;
ListNode *behind = right->next;
// 逆序执行
reverse_list(left, right);
// 插入回去
prev->next = right;
left->next = behind;
// 防止内存泄漏
ListNode *tmp = vhead->next;
vhead->next = nullptr;
delete vhead;
return tmp;
}
160. 相交链表
- letcode题目链接
- 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
- 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
- 思路
- 哈希缓存:先将一个链表结点全部缓存到哈希表中,然后另一个链表遍历每个结点判断是否在哈希表中
- 栈:两个链表从公共结点开始后面都是一样的,若是我们顺着链表从后向前查找,很容易就能查找到链表的公共结点(第一个不相同的结点的下一个结点即所求)
- 同步移动:计算两个链表的长度差值,然后进行同步移动
- 交替移动
- 若两链表没有公共结点,那么两个链表指针都会走过 s1+s2个结点,同时到达两链表末尾
- 若有公共结点,由于最后会同时走到两链表终点,所以倒退回去,两个指针一定会在第一个公共结点处相遇
- 当然,若两链表等长,那确实不会跳到另一链表,不过链表等长本身指针就是同步的,同样也能找到公共结点
// 哈希缓存
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode*> uset;
// 放入缓存中
while (headA != nullptr) {
uset.insert(headA);
headA = headA->next;
}
// 查找缓存
while (headB != nullptr) {
if (uset.count(headB)) return headB;
headB = headB->next;
}
return nullptr;
}
// 交替移动?
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pa = headA;
ListNode *pb = headB;
while (pa != pb) {
(pa == nullptr) ? pa = headB : pa = pa->next;
(pb == nullptr) ? pb = headA : pb = pb->next;
}
return pa;
}
23. 合并K个排序链表
- 归并法
//通过mid将数组一分为二,并不断缩小规模,当规模为1时返回并开始合并
//通过合并两个链表,不断增大其规模,整体看就是不断缩小-最后不断扩大的过程
ListNode helper(ListNode[] lists, int begin, int end) {
if(begin==end) {
return lists[begin];
}
int mid = begin+(end-begin)/2;
ListNode left = helper(lists,begin,mid);
ListNode right = helper(lists,mid+1,end);
return merge(left,right);
}
//合并两个有序链表
ListNode merge(ListNode a, ListNode b) {
if(a==null || b==null) {
return (a==null) ? b : a;
}
if(a.val<=b.val) {
a.next = merge(a.next,b);
return a;
} else {
b.next = merge(a,b.next);
return b;
}
}
- 逐个合并
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto merge = [](ListNode *l1, ListNode *l2)->ListNode *{
ListNode *vhead = new ListNode(-1, nullptr);
ListNode *p = vhead;
while (l1 && l2) {
if (l1->val > l2->val) {
p->next = l2;
p = p->next;
l2 = l2->next;
} else {
p->next = l1;
p = p->next;
l1 = l1->next;
}
}
p->next = (l1 ? l1 : l2);
return vhead->next;
};
// 逐个合并
if (lists.size() == 0) return nullptr;
ListNode *l1 = lists[0];
for (int i = 1; i < lists.size(); ++i) {
if (lists[i] != nullptr){
l1 = merge(l1, lists[i]);
}
}
return l1;
}
143. 重排链表
- 题目
void reorderList(ListNode* head) {
// 寻找中间结点(前一个)模板
ListNode *slow = head;
ListNode *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// 拆分链表并将后半部分压入栈中
ListNode *second_head = slow->next;
slow->next = nullptr;
stack<ListNode*> st;
while (second_head != nullptr) {
st.push(second_head);
second_head = second_head->next;
}
// 合并链表
ListNode *cur = head;
while (!st.empty()) {
ListNode *tmp = st.top();
st.pop();
tmp->next = cur->next;
cur->next = tmp;
cur = cur->next->next;
}
}
142. 环形链表 II
- 题目
- 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
ListNode *detectCycle(ListNode *head) {
// 快慢指针
ListNode* fast = head;
ListNode* slow = head;
while (true) {
if (fast == nullptr || fast->next == nullptr) return nullptr;
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
// 第一次相遇后,快指针赋值为头部,然后再同步走,直到相等
fast = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
19. 删除链表的倒数第 N 个结点
- 有可能删除头结点的情况,都需要增加虚拟头节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(n < 0 || head == nullptr)
return nullptr;
// 快慢指针拉开n个节点的距离
ListNode *vHead = new ListNode(0);
vHead->next = head;
ListNode *slow = vHead;
ListNode *fast = vHead;
// 让slow指向被删除节点的前一个
while(n--){
fast = fast->next;
}
// 同步移动
while(fast->next != nullptr){
fast = fast->next;
slow = slow->next;
}
// 删除节点
slow->next = slow->next->next;
return vHead->next;
}
移除链表中的重复结点
LinkList *DeleteSameNode(LinkList *head) {
LinkList *vhead = new LinkList(0);
vhead->next = head;
// 删除cur->next中剩下的值为val的结点
auto delete_node = [](int val, LinkList *cur){
while (cur->next != nullptr) {
if (cur->next->val == val) {
LinkList *tmp = cur->next;
cur = cur->next->next;
delete tmp;
}
cur = cur->next;
}
};
// 遍历链表,删除重复结点
LinkList *cur = vhead;
while (cur->next != nullptr) {
delete_node(cur->next->val, cur);
cur = cur->next;
}
}
删除无序链表中值重复出现的节点
-
采用哈希表
set
性质进行单一化,然后进行新建。- 空间复杂度:O(n)
- 时间复杂度:O(n)
-
使用
unordered_set<int> s;
记录曾经出现过的情况,通过s.find(val) != s.end()
实现对过去历史的快速查找。#include <set> void deleteDuplicates(ListNode* head) { if (head == nullptr) return ; std::unordered_set<int> s; // 用于存储出现过的节点值 // key:处理头节点,从而不需要建立vhead,但是头节点必须不会被删除 s.insert(head->val); // 先将头节点的值插入 set ListNode* cur = head; while (cur->next != nullptr) { if (s.find(cur->next->val) != s.end()) { // 如果下一个节点的值在 set 中出现过,删除下一个节点 ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; } else { // 否则将下一个节点的值插入 set 中,继续遍历 s.insert(cur->next->val); cur = cur->next; } } }
-
采用双重链表遍历,每次排除一个元素的其他重复结点
- 空间复杂度:O(1)
- 时间复杂度:O(n^2)
void deleteDuplicates(ListNode* head) { if (head == nullptr) { return; } ListNode* cur = head; while (cur != nullptr) { // key:使用了当前遍历法,cur ListNode* prev = cur; ListNode* next = cur->next; while (next != nullptr) { // key:使用了前者遍历法,cur->next if (next->val == cur->val) { // 如果下一个节点的值与当前节点的值相同,删除下一个节点 prev->next = next->next; delete next; next = prev->next; } else { // 否则继续向后遍历 prev = next; next = next->next; } } cur = cur->next; } }
🚩点此跳转到首行↩︎