9.25度小满一面

1.map的底层

2.unorder_map哈希表有自己实现过吗？哈希冲突

3.poll和epoll和select的优缺点、

4.线程同步机制是用来做什么的?

5.五子棋项目问题--

算法题:

6.LeetCode.重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：  L0 → L1 → … → Ln-1 → Ln  请将其重新排列后变为： L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

平时真的应该好好练算法 ，当时就给十分钟，没撕出来，wwww~~~~

思路:这道题就是相当于将三个简单题结合起来了，分别是

876.链表的中间节点

这里要明白一个概念，定义快慢指针，同时指向头结点，让它们俩同时移动，slow移动一个节点，fast移动两个节点，当fast指向空时，slow一定指向中间节点。是因为每次fast比slow快移动一个，fast的速度是slow的2倍，而当fast指向末尾时，slow刚好移动fast的一半距离，所以说slow指向了链表的中间节点。

206.翻转链表

最后就是合并链表

将这个题拆分一下就不难了，首先是找到链表的中间节点，

 ListNode* findMid(ListNode* head){//找到中间节点ListNode* slow=head;ListNode* fast=head;while(fast!=nullptr&&fast->next!=nullptr){fast=fast->next->next;slow=slow->next;}return slow;}

 然后是翻转链表

  ListNode* reverseList(ListNode* head){//翻转后端节点ListNode* prev=nullptr;ListNode* cur=head;while(cur!=nullptr){ListNode* temp=cur->next;cur->next=prev;prev=cur;cur=temp;}return prev;}

 最后是合并链表，合并链表的思想如下图所示

首先，将中点作为头结点，然后将后端链表进行翻转，

代码如下所示:

合并思路跟上面的黄线是一样的。要注意通过l1_temp来存储l1的下一个节点的地址，防止丢失

 void merge(ListNode* l1,ListNode* l2){ListNode* l1_temp;ListNode* l2_temp;while(l1!=nullptr&&l2!=nullptr){l1_temp=l1->next;l2_temp=l2->next;l1->next=l2;l1=l1_temp;l2->next=l1;l2=l2_temp;}}