每日算法题：Day 8
作者：TeddyZhang，公众号：算法工程师之路
Day 8, C/C++知识点走起~
1
编程题
【剑指Offer】翻转链表
输入一个链表，反转链表后，输出新链表的表头。
思路： 第一种思路，使用一个堆栈去保存所有的节点，然后再进行依次弹出后并连接起来即可！
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
stack<ListNode*> sta;
ListNode* cur = pHead;
ListNode* newHead; // 要返回的头结点
if(pHead == nullptr || pHead->next == nullptr){
return pHead;
}
while(cur->next != nullptr){
sta.push(cur);
cur = cur->next;
}
newHead = cur; // 最后一个节点为新链表的头结点
while(!sta.empty()){
cur->next = sta.top();
sta.pop();
cur = cur->next;
}
cur->next = nullptr;
return newHead;
}
};
如果不使用额外的空间的话，我们可以使用两个指针pre和next, 对链表相邻的两个节点进行交换调整，这才是面试官想要看到的算法！循环中主要有四步：
- 保存当前节点的next节点，下一步要改变，需要保存
- 修改当前节点的next节点为pre（前驱节点）
- pre指针直到当前节点
- pHead指针指向next节点（向后移动）
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == nullptr || pHead->next == nullptr){
return pHead;
}
ListNode* pre = nullptr;
ListNode* next = nullptr;
while(pHead != nullptr){
next = pHead->next; // 保存next节点，因为下一步要修改pHead.next
pHead->next = pre; // 第一次pre=null,即第一个节点指向空
pre = pHead;
pHead = next;
}
return pre;
}
};
【剑指Offer】合并两个排序链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路： 这个思路应该都可以想到归并排序的方法，然后进行组合形成最终的链表，需要注意的是，由于pHead1和pHead2的第一个链表节点谁大谁小不确定，因此头结点无法确定，因此我们需要新建一个哨兵节点pHead，用来创建一个链表的首节点,最终返回pHead.next为真正的头结点！
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* pHead = new ListNode(-1);
ListNode* cur = pHead;
while(pHead1 != nullptr && pHead2 != nullptr){
if(pHead1->val < pHead2->val){
cur->next = pHead1; // 新链表头结点
pHead1 = pHead1->next;
}else{
cur->next = pHead2;
pHead2 = pHead2->next;
}
cur = cur->next;
}
if(pHead1 != nullptr){
cur->next = pHead1;
}
if(pHead2 != nullptr){
cur->next = pHead2;
}
return pHead->next;
}
};2
概念题
【C/C++】区分以下几个语句，表示什么？
int *p[]
int (*p)[]
int *p(int)
int (*p)(int)
前两个分别为指针数组和数组指针，区别就是当将p用小括号加以强调，表示这是一个指针！其中指针数组表示这是一个数组，只不过数组中的元素都是int的指针类型。而数组指针返回是一个指向包含有5个int类型的数组，但这个数组没有名字，为一个匿名数组！举例子:
int arr[]={，，，，};
int (*p1)[] = &arr;
后两个分别是普通指针函数和函数指针，前者实质上是一个普通函数，参数是int类型，返回值为一个指针。而函数指针实质上是一个指针变量，指向一个函数的地址，其基本声明类型如下:
返回值+（*函数名）+（参数类型1，参数类型2…）
int add(int x,int y)
{
return x + y;
}
int (*fun)(int, int);
fun = &add; // 将fun函数指针指向add
【C/C++】野指针的成因，危害及避免方法？
产生的原因：
- 指针定义时没有初始化，默认指向随机区域
- 指针指向一片内存，当内存释放（delete或者free操作）时，没有将指针置空或者其他复制操作！
- 返回一个指向栈内存的指针，由于栈内存在函数结束后会被释放，从而形成野指针
危害：
- 指向不可访问区域，报错
- 指向一个可访问，但数据错误的地方，可以带来调试错误，难以发现问题所在
- 指向正在使用的空间，可能会修改这个空间的值，造成程序崩溃
避免方法：
- 定义时初始化，当释放内存时，记得指针指向nullptr
- 不要在函数中返回栈空间的引用或指针
- 使用前对指针进行合法性的判断
【C/C++】堆和栈的区别有哪些？
在C++中，内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
栈，就是那些由编译器在需要的时候分配，在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等，栈的地址分配是连续的，空间较小，几兆，大数据的话还是分配堆比较好些。
堆，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉(一般都要释放，不然程序运行下去会崩溃)，那么在程序结束后，操作系统会自动回收，堆的地址分配是不连续的，但空间较大。