关键词：
高频面试题之链表专题公开课（二）
本节目标
-
1、逆置一个单链表。（2020年阿里巴巴二面原题）
-
2、判断单链表是否是回文结构。（2019年字节跳动二面原题）
-
3、删除一个有序单链表中的重复节点。（2019年字节跳动二面原题）
-
4、复杂链表的复制。（2020年百度二面原题）
1、逆置一个单链表。
OJ链接：https://leetcode-cn.com/problems/reverse-linked-list/description/
高频考察的大厂云图：
解题思路：
- 三指针翻转法：记录连续的三个节点，原地修改节点指向的方向。
- 头插法：取下原链表的每个节点都进行头插到新链表。
代码实现：
// 三个指针翻转的思路
/**
* Definition for singly-linked list.
* struct ListNode
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL)
* ;
*/
class Solution
public:
ListNode* reverseList(ListNode* head)
// 链表为空或者只有一个节点不需要翻转
if(head == NULL || head->next == NULL)
return head;
ListNode* n1, *n2, *n3;
n1 = NULL;
n2 = head;
n3 = n2->next;
//中间节点不为空，继续修改指向
while(n2)
//中间节点指向反转
n2->next = n1;
//更新三个连续的节点
n1 = n2;
n2 = n3;
// 需要注意到最后两个节点时，n3已经为空
if(n3)
n3 = n3->next;
//返回新的头
return n1;
;
// 头插的思路
/**
* Definition for singly-linked list.
* struct ListNode
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL)
* ;
*/
class Solution
public:
ListNode* reverseList(ListNode* head)
ListNode* newhead = NULL;
ListNode* cur = head;
while(cur)
struct ListNode* next = cur->next;
//头插新节点，更新头
cur->next = newhead;
newhead = cur;
cur = next;
return newhead;
;2、判断单链表是否是回文结构。
OJ链接：https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
高频考察的大厂云图：
解题思路：
需要注意本题要求了复杂度为O(N)，空间复杂度为O(1)
1、本题说明了链表的长度小于900，所以这里我们可以开辟一个900个空间的数组，将链表的数据放到数组中再进行判断。这种方法虽然能过OJ，但是实际面试中是不符合面试官的要求的。
2、通过slow走一步，fast走两步，找到中间节点。然后将后半段链表反转，反转后的链表跟原链表对比是否相同，相同则是回文结构。这样写才满足上面的对复杂度的要求。
代码实现：
/*
此题也可以先把链表中的元素值全部保存到数组中，然后再判断数组是否为回文。不建议使用这种解法，因为如果没有告诉链表最大长度，则不能同此解法
*/
class PalindromeList
public:
bool chkPalindrome(ListNode* A)
// write code here
int a[900] = 0;
ListNode* cur = A;
int n = 0;
//保存链表元素
while(cur)
a[n++] = cur->val;
cur = cur->next;
//判断数组是否为回文结构
int begin = 0, end = n-1;
while(begin < end)
if(a[begin] != a[end])
return false;
++begin;
--end;
return true;
;
/*
解题思路：
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
*/
class PalindromeList
public:
bool chkPalindrome(ListNode* A)
if (A == NULL || A->next == NULL)
return true;
ListNode* slow, *fast, *prev, *cur, *nxt;
slow = fast = A;
//找到中间节点
while (fast && fast->next)
slow = slow->next;
fast = fast->next->next;
prev = NULL;
//后半部分逆置
cur = slow;
while (cur)
nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
//逐点比对
while (A && prev)
if (A->val != prev->val)
return false;
A = A->next;
prev = prev->next;
return true;
;3、删除一个有序单链表中的重复节点。
高频考察的大厂云图：
解题思路：
- 定义三个指针n1、n2、n3，使用n2和n3去找链表中的重复阶段区间段，找到以后，删除n2到n3中间的重复区间，然后让n1，链接上重复区间后面一段。再继续往后找重复区间，再重复上面的过程。ps：需要注意的是本题逻辑并不难，但是代码控制中有很多边界条件需要注意，控制不好，代码很容易崩溃。
代码实现：
/*
struct ListNode
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL)
;
*/
/*
解题思路：
此题可以先找出相同节点的区间，然后删除区间中的所有值，直到把链表遍历完结束
*/
class Solution
public:
ListNode* deleteDuplication(ListNode* pHead)
if(pHead == NULL || pHead->next == NULL)
return pHead;
ListNode* n1 = NULL;
ListNode* n2 = pHead;
ListNode* n3 = n2->next;
while(n3 != NULL)
//如果相邻节点不相同，则不需要删除，更新节点，继续向后遍历
if(n2->val != n3->val)
n1 = n2;
n2 = n3;
n3 = n3->next;
else
//如果相邻节点相同
//则n3去找第一个不相同的节点
while(n3 && n3->val == n2->val)
n3 = n3->next;
//重新链接，如果要删除的包括头节点，则更新头节点
if(n1)
n1->next = n3;
else
pHead = n3;
// 删除掉重复的节点
while(n2 != n3)
ListNode* next = n2->next;
delete n2;
n2 = next;
//更新节点
n2 = n3;
if(n3)
n3 = n3->next;
return pHead;
;4、复杂链表的复制
OJ链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/description/
高频考察的大厂云图：
解题思路：
此题可以分三步进行：
- 拷贝链表的每一个节点，拷贝的节点先链接到原链表被拷贝节点的后面
- 处理拷贝节点的random指针：拷贝节点的random指针指向被拷贝节点随机指针的下一个位置
- 拆解链表，把拷贝的链表从原链表中拆解出来，再链接出拷贝链表
代码实现：
/*
// Definition for a Node.
class Node
public:
int val;
Node* next;
Node* random;
Node(int _val)
val = _val;
next = NULL;
random = NULL;
;
*/
class Solution
public:
Node* copyRandomList(Node* head)
// 1.拷贝链表，并插入到原节点的后面
Node* cur = head;
while(cur)
Node* copy = new Node(cur->val);
Node* next = cur->next;
// 插入
cur->next = copy;
copy->next = next;
// 迭代往下走
cur = next;
// 2.置拷贝节点的random
cur = head;
while(cur)
Node* copy = cur->next;
if(cur->random != NULL)
copy->random = cur->random->next;
else
copy->random = NULL;
cur = copy->next;
// 3.解拷贝节点，链接拷贝节点
Node* copyHead = NULL, *copyTail = NULL;
cur = head;
while(cur)
Node* copy = cur->next;
Node* next = copy->next;
// copy解下来尾插链接到拷贝节点
if(copyTail == NULL)
copyHead = copyTail = copy;
else
copyTail->next = copy;
copyTail = copy;
cur->next = next;
cur = next;
return copyHead;
;/*思路跟上面的方法基本一致，差别不再是拷贝节点挂在原节点后面建立映射关系，而是通过将原节点和拷贝节点存储到map中建立映射关系，这样也是通过3步就可以复制出拷贝链表*/
// 1.拷贝链表,使用map建立原链表节点和拷贝节点的映射
// 2.置拷贝节点的random. 通过map找到node->random的拷贝节点，就可以值copy节点的random。
// 3.从map中找到拷贝节点，链接拷贝节点
// Definition for a Node.
class Node
public:
int val;
Node* next;
Node* random;
Node(int _val)
val = _val;
next = NULL;
random = NULL;
;
*/
class Solution
public:
Node* copyRandomList(Node* head)
map<Node*, Node*> nodeCopyMap;
// 1.拷贝链表,使用map建立原链表节点和拷贝节点的映射
Node* cur = head;
while(cur)
Node* copy = new Node(cur->val);
nodeCopyMap[cur] = copy;
cur = cur->next;
// 2.置拷贝节点的random
cur = head;
while(cur)
Node* copy = nodeCopyMap[cur];
if(cur->random != NULL)
copy->random = nodeCopyMap[cur->random];
else
copy->random = NULL;
cur = cur->next;
// 3.从map中找到拷贝节点，链接拷贝节点
Node* copyHead = NULL, *copyTail = NULL;
cur = head;
while(cur)
// 找到cur映射的拷贝节点
Node* copy = nodeCopyMap[cur];
if(copyTail == NULL)
copyHead = copyTail = copy;
else
copyTail->next = copy;
copyTail = copy;
cur = cur->next;
return copyHead;
;如果你看了以后不是很明白，你可以点击看下面的视频讲解：
视频讲解（鼠标点这里）
深度分享：面试阿里，字节跳动，美团90%会被问到的hashmap知识(代码片段)
一，HashTable哈希表，它相比于hashMap结构简单点，它没有涉及红黑树，直接使用链表的方式解决哈希冲突。我们看它的字段，和hashMap差不多，使用table存放元素privatetransientEntry<?,?>[]table;privatetransientintcount;privateintthreshold;private... 查看详情
真香！百度阿里腾讯字节跳动等面试题库，被各大厂要求直接下架
前言Android面试题解析主要内容包括Java知识汇总、Android知识汇总、Android拓展知识点、Android开源库源码分析、设计模式汇总、Gradle知识点汇总、常见面试算法题汇总等等。解析百度、阿里、腾讯大厂面试被问到的题目，也涵... 查看详情
字节跳动高频算法题top100
题目出现次数3.无重复字符的最长子串10625.K个一组翻转链表84206.反转链表83215.数组中的第K个最大元素81146.LRU缓存机制68103.二叉树的锯齿形层次遍历6415.三数之和62121.买卖股票的最佳时机61160.相交链表581.两数之和48236.二叉树的最... 查看详情
阿里字节：高效ios面试题之block(代码片段)
👇👇关注后回复 “进群” ，拉你进程序员交流群👇👇来源；https://www.sunyazhou.com/2020/09/Block/block这一篇我们来研究一下objc的block并回答一下面试中的下列问题:block的内部实现，结构体是什么样的block... 查看详情
工作三年终于社招进字节跳动！字节跳动，阿里，腾讯java岗面试经验汇总
...补充基础知识等。也是有些辛苦。终于是在前不久拿到了字节跳动的offer，现在我也来写面经，希望能帮助到大家！面经Java基础0.HashMap的源码，实现原理，JDK8中对HashMap做了怎样的优化。拉链结构，数组+链表，原理是hash找数组... 查看详情
java面试者的经历，吐血分享字节跳动的java面试经验技巧
...享一份资深Java面试官整理的「 大厂高频核心面试题 」字节跳动面试题Http协议cookiesession介绍一下session表结构怎么设计，储存在哪里？你们的sessioncookie在项目里运用到哪里？算法题：[删除链表中重复的节点]在... 查看详情
常见的链表翻转，字节跳动加了个条件，面试者高呼：我太难了！(代码片段)
一.序我又来讲链表题了，这道题据说是来自字节跳动的面试题。为什么说是「据说」呢？因为我也是看来的，觉得题目还是挺有意思，但是原作者给出的方案，我想了想觉得还有优化空间，就单独拿出来... 查看详情
字节跳动高频算法题top100
题目出现次数3.无重复字符的最长子串10625.K个一组翻转链表84206.反转链表83215.数组中的第K个最大元素81146.LRU缓存机制68103.二叉树的锯齿形层次遍历6415.三数之和62121.买卖股票的最佳时机61160.相交链表581.两数之和48236.二叉树的最... 查看详情
字节跳动高频算法题top100
题目出现次数3.无重复字符的最长子串10625.K个一组翻转链表84206.反转链表83215.数组中的第K个最大元素81146.LRU缓存机制68103.二叉树的锯齿形层次遍历6415.三数之和62121.买卖股票的最佳时机61160.相交链表581.两数之和48236.二叉树的最... 查看详情
面试阿里，字节跳动，腾讯90%会被问到的面试题——单例模式(代码片段)
1.什么是Singleton？Singleton，即单例，在Java中表示的是单例模式，所谓的单例模式，指的就是在程序中，有且仅有一个该实例对象。单：唯一，单独。例：实例对象。2.单例模式有几种创建方式？2.1饿汉式（在程序启动过程中，就... 查看详情
阿里字节腾讯等大厂java岗mysql面试高频面试题整理(代码片段)
索引相关1.什么是索引?索引是一种数据结构,可以帮助我们快速的进行数据的查找.2.索引是个什么样的数据结构呢?索引的数据结构和具体存储引擎的实现有关,在MySQL中使用较多的索引有Hash索引,B+树索引等,而我们经常使用的Inno... 查看详情
剑指offer之链表(代码片段)
//剑指offer之链表//面试题6从尾到头打印链表/*****************************************************************************************问题描述：输入一个链表的头节点，从尾到头反过来打印出每个节点的值链表节点定义如下：structListNodeintm_nValue;Lis... 查看详情
ios经典面试题之深入分析block相关高频面试题(代码片段)
一、前言本文重点来研究一下objc的block，并具体来分析一下以下一些面试题目：block的内部实现，结构体是什么样？block是类吗？有哪些类型？一个int变量被__block修饰与否的区别？block的变量如何截获&#x... 查看详情
25.k个一组翻转链表(困难)-字节跳动高频题(代码片段)
一、题目描述给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。进阶：... 查看详情
2022暑期实习字节跳动数据研发面试经历
🌟今天下午面试两家，字节跳动数据研发一面和百度三面，百度那边突然不面了，hr说下个星期再看看，是直接过了还是再来一面，需要和部门商量一下，先来总结一下字节跳动的面试，对百度面... 查看详情
高频面试题之jvm灵魂拷问，21题带你通关！(代码片段)
这是本期的JVM面试题目录，不会的快快查漏补缺~1.什么是JVM内存结构？jvm将虚拟机分为5大区域，程序计数器、虚拟机栈、本地方法栈、java堆、方法区；程序计数器：线程私有的，是一块很小的内存空间... 查看详情
字节跳动笔试题:链表反转(代码片段)
...职大厂不可或缺的基本能力。最近就听群里的伙伴说面试字节跳动的时候要求现场写出以k个为一组反转链表，如果不做准备，之前没有一点了解，看到这种题目，很容易懵逼，那么肯定就必挂无疑了。算法的种类很多,数组、链... 查看详情
深度分析：面试阿里，字节跳动，美团几乎都会被问到的阻塞队列(代码片段)
基本概念阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。这两个附加的操作支持阻塞的插入和移除方法。1）支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满。2）支持阻塞的移除方... 查看详情