面试真题

结论：数据结构分线性、树、图、哈希等，应届生应掌握数组、链表、栈、队列、哈希表、二叉树、堆。核心要点：数组随机访问O(1)但增删慢；链表插入删除O(1)但查找慢；栈用于递归与括号匹配；队列支撑BFS与缓冲；哈希表平均O(…

🎤 小鹏汽车

反转链表即将单向链表指针方向完全颠倒，原头节点变尾节点，原尾节点变头节点。核心方法：1.迭代法（三指针）：用pre、cur、nxt指针，初始pre=null，cur=head；遍历时nxt=cur.next保存后继，cu…

🎤 百度

结论：环形链表环长可用快慢指针在O(1)空间求得：先找相遇点再测长。核心要点：1.快慢指针从头起步，快2步慢1步，有环必相遇；2.相遇后慢指针不动，快指针改1步/次前进并计数；3.快再次到慢位置，计数即环长L；原理：相遇…

🎤 京东

结论：快排是分治排序，选基准分区递归；平均时间O(n log n)最坏O(n^2)。原理：1.选pivot将比它小放左大放右，递归子数组；2.若选端点且数组有序，每次只减一元素导致O(n^2)，随机或三数取中可避；3.时…

🎤 京东

结论：无头指针删除给定节点，采用复制下一节点值并删除下一节点的方法。核心原理：因无法访问前驱，直接将当前节点值替换为下一节点值，再跳过并删除下一节点（node->val = node->next->val; node->…

🎤 腾讯

结论：通过迭代或递归反转单链表，使头节点变为尾节点。核心要点：1. 迭代法使用pre、cur、next三指针，遍历时令cur.next=pre，然后三者后移，最后pre为新头；2. 递归法递归到尾节点，回溯时令head.…

🎤 京东

结论：用哈希表统计频次，输出次数大于1的数字及出现次数。核心要点：1. 创建HashMap<Integer,Integer>；2. 遍历数组，map.put(num, map.getOrDefault(num,0)+1)…

🎤 京东

结论：迭代法用三指针（prev,cur,next）遍历反转；递归法先递归到尾节点再从后往前反转指针。原理：迭代初始化prev=null,cur=head；循环中保存next=cur.next，cur.next=prev，…

🎤 腾讯

结论：使用队列BFS，空节点也入队用'*'占位以表达结构。原理：初始化队列推入root；按层处理，记录当前层节点数，出队时若节点空则追加'*'且不推孩子，否则追加值并推入左右孩子（含null）；这样完整占位。对比DFS不…

🎤 腾讯

结论：单链表反转可用迭代或递归，迭代法空间O(1)最优。核心要点：迭代用三指针prev、cur、next；初始prev=null，cur=head；循环：next=cur.next暂存，cur.next=prev反转指向…

🎤 字节跳动

结论：镜像二叉树即将每个节点的左右子树互换，得到原树的镜像。核心要点：采用递归，若当前节点为空直接返回；否则递归镜像左子树和右子树，然后交换当前节点的左右指针；也可使用层序遍历（队列）逐个交换节点左右孩子。本质是对树中所…

🎤 字节跳动

结论：求两单链表相交的起始节点，最优用双指针法，时间O(n)空间O(1)。核心要点：设链表A长度a+c，B长度b+c，c为公共尾部；指针pA从A头走，到尾后跳到B头；pB从B头走，到尾后跳到A头；因pA走a+c+b，pB…

🎤 字节跳动

结论：有序数组去重可用快慢指针原地完成，慢指针维护无重复前缀，返回新长度。核心要点：慢指针slow初始化0，快指针fast从1遍历；当nums[fast]!=nums[slow]时slow前移并赋值nums[slow]=…

🎤 腾讯

结论：跳表（Skip List）是一种支持有序元素快速查找的随机化数据结构，可视为加了多层索引的链表。原理：底层为有序单向链表；每个节点以概率p（常用0.25或0.5）晋升到上一层，形成稀疏索引；查找时从最高层向右，遇较…

🎤 腾讯

结论：DFS适合深度探索、连通性、回溯、拓扑排序；BFS适合无权图最短路径、层序遍历、最小步数。原理：DFS用栈或递归深入到底再回溯，空间复杂度O(深度)；BFS用队列逐层扩展，首次访问即最短路径，空间可能更大。对比：找…

🎤 腾讯

结论：快慢指针判环并求环大小。要点：1.快指针步2慢指针步1同起点，相遇则有环，快到null无环；2.求环长：相遇后快指针改步1，慢不动，再次相遇步数即环节点数；或两指针继续走，再次相遇步数即环长；3.原理：环内速度差1…

🎤 京东

结论：哈希冲突指不同关键字经哈希函数得到相同存储地址，无法避免但可解决。常用方法：1. 链地址法：每个桶挂链表或红黑树（如HashMap），冲突时追加节点，查询遍历；2. 开放寻址法：线性探测、平方探测或双重哈希，冲突后…

🎤 百度