我要出去乱说

分类

C++(2) 程序员代码面试指南(20) 题解(2)

/ 注册

TA的专栏 50篇文章 3人订阅

程序员代码面试指南（C++版题解）

41篇文章 592人学习

我的面经汇总

9篇文章 21587人学习

全部文章（共42篇）

程序员代码面试指南 2.17：一种怪异的节点删除方式来自专栏

1、思路不给链表的头结点，只给其中一个节点，要求删除这个节点（题目保证要删除的节点不是链表的尾结点）；将下一节点的值赋给当前节点，并跳过下一节点即可。 void remove_node_wired(list_node * node) { if (node == nullptr) ...

C++

2022-05-07

1 270

程序员代码面试指南 2.16：单链表的选择排序来自专栏

1、思路将链表分为已排序和未排序两个部分，循环遍历未排序部分找到最小值，将其从未排序链表中删除并添加到已排序链表末尾；为了实现删除最小值节点的操作，需要保存最小值节点的前一个节点；时间复杂度为，空间复杂度为。 2、代码 //在未排序链表中找到最小值节点的前一个节点 list_n...

C++

2022-05-07

1 328

程序员代码面试指南 2.14：在链表中删除指定值的节点来自专栏

1、思路用两个指针pre和cur来标记前一个节点和当前节点，若当前节点值为要删除的指定值，则将pre的下一节点指向cur的下一节点，即跳过当前节点；时间复杂度，空间复杂度。 2、代码 list_node * remove_value(list_node * head, int n...

C++

2022-05-02

1 381

程序员代码面试指南 2.13：删除无序链表中值重复出现的节点来自专栏

解法一：哈希 1、思路遍历链表的过程中，将元素的值存入哈希表内，遇到相同值的节点跳过即可；时间复杂度，空间复杂度。 list_node * remove_rep(list_node * head) { if (head == nullptr || head->next...

C++

2022-05-02

1 370

程序员代码面试指南 2.12：将单链表的每K个节点之间逆序来自专栏

1、思路用双指针标记链表中每段为K个节点长度的首尾节点，反转当前段，保存当前段反转后的头结点newHead，递归进入下一段的反转；若tail尾结点已经指向空，则返回链表。 2、代码 list_node* reverse(list_node* head, list_node* tail) ...

C++

2022-04-28

1 316

程序员代码面试指南 2.10：两个单链表生成相加链表来自专栏

1、思路先把两个链表反转，从低位开始相加；相加完毕后，再将链表反转即可。 2、代码 list_node* reverseList(list_node* head) //反转链表 { if (head == nullptr) return nullptr; au...

C++

2022-04-25

1 297

程序员代码面试指南 2.8：将单链表按值划分来自专栏

解法一：暴力 1、思路把链表值全部复制到vector中，通过sort排序，然后遍历打印数值；时间复杂度 O(N)O(N)O(N)，空间复杂度 O(N)O(N)O(N) 。 2、代码 list_node * list_partition(list_node * head, int pi...

C++

2022-04-24

1 217

程序员代码面试指南 2.7：判断一个链表是否为回文结构来自专栏

解法一：栈 1、思路遍历链表放入栈中，弹出栈元素的同时从头遍历链表，比较栈顶元素与链表当前元素是否相等即可；时间复杂度，空间复杂度。 2、代码 list_node * check(list_node * head) { if (head == nullptr || hea...

C++

2022-04-15

1 337

程序员代码面试指南 2.6：环形链表的约瑟夫问题来自专栏

解法一 1、思路遍历环形链表，删除每 m 个节点，直到链表中剩下一个元素为止；一共要删除 n - 1 个节点，每次删除要遍历 m 次，时间复杂度为，略高。 2、代码 #include <iostream> #include <memory> using na...

C++

2022-04-14

1 464

程序员代码面试指南 2.5：反转部分单向链表来自专栏

1、思路需要得到四个节点的位置：反转链表的前一个节点before，反转链表的起始节点start，反转链表的末尾结点end以及反转链表末尾结点的后一个节点after；将start与end之间的链表进行反转，反转后end变成了表头，start变成了表尾；最后再将这四个节点连接起来即可。 ...

C++

2022-04-13

1 349