秋招之路-链表面试题集合(二)

2024-08-27 01:38

本文主要是介绍秋招之路-链表面试题集合(二),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[图]program 2019-07-24

这是 herongwei 的第 80 篇原创

阅读本文大概需要 8.88 分钟

前言

链表是最基本的数据结构,面试官也常常用链表来考察面试者的基本能力,链表的操作也离不开指针,指针又很容易导致出错。综合多方面的原因,链表题目在面试中占据着很重要的地位。这里总结常见的链表面试题,希望对你有所帮助!

今天的题目

1、在 O(1) 时间删除链表节点。

2、输入一个链表,输出该链表中倒数第k个结点。

3、输入一个链表,输出该链表中间的结点。

4、判断一个链表是否是回文链表。

5、从有序链表中删除重复节点。

6、删除链表的倒数第 n 个节点。

7、交换链表中的相邻结点。

8、链表元素按奇偶聚集。

9、链表求和。

10、分割链表。

1、在 O(1) 时间删除链表节点

分析:

容易想到的一个思路:用下一个节点数据覆盖要删除的节点,然后删除下一个节点。当然,在删除之前,我们需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时,时间复杂度为 O(1)。

上面的思路还有一个问题:如果删除的结点位于链表的尾部,没有下一个结点,怎么办?我们仍然从链表的头结点开始,顺序遍历得到给定结点的前序结点,并完成删除操作。这个时候时间复杂度是 O(n)。

如果题目要求我们需要在 O(1) 时间完成删除操作,我们的算法是不是不符合要求?实际上,假设链表总共有 n 个结点,我们的算法在 n-1 总情况下时间复杂度是 O(1),只有当给定的结点处于链表末尾的时候,时间复杂度为 O(n)。那么平均时间复杂度

[(n-1)*O(1)+O(n)]/n,仍然为 O(1)。

参考代码:

class Solution {
public:void delListNode(ListNode* pHead, ListNode* pDelNode) {if(pHead == nullptr)return;if(pDelNode->next == nullptr) { //删除的结点位于链表的尾部ListNode* pCur = pHead;while(pCur->next != pDelNode) {pCur = pCur->next;}pCur->next = nullptr;delete pDelNode;pDelNode = nullptr;}else { //用下一个节点数据覆盖要删除的节点,然后删除下一个节点ListNode *pNext = pDelNode->next;pDelNode->val   = pNext->val;pDelNode->next  = pNext->next;delete pNext;pNext = nullptr;}}
};

2、输入一个链表,输出该链表中倒数第 k 个结点

示例1
输入
8
1 2 3 4 5 6 7 8
4
输出
5

分析:

设置两个指针,p2 指针先走(k-1)步,然后再一起走,当 p2 走到最后时,p1 就为倒数第k个数。

参考代码:

class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {if(pListHead == nullptr|| k == 0)return nullptr;ListNode* pTail = pListHead;ListNode* pHead = pListHead;for(int i=1; i<k; ++i) {if(pHead->next != nullptr)pHead = pHead->next;elsereturn nullptr;}while(pHead->next != nullptr) {pHead = pHead->next;pTail = pTail->next;}return pTail;}
};

3、输入一个链表,输出该链表中间的结点

Example 1:Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

分析:

求链表的中间节点,如果链表的长度为偶数,返回中间两个节点的任意一个,若为奇数,则返回中间节点。

很容易想到,如果可以求链表的长度的话,那么计算出中间节点所在链表顺序的位置即可。但是如果要求只能扫描一遍链表,如何解决呢?最高效的解法和第 2 题一样,通过两个指针来完成。用两个指针从链表头节点开始,一个指针每次向后移动两步,一个每次移动一步,直到快指针移到到尾节点,那么慢指针即是所求。

参考代码:

class Solution {
public:ListNode *getMiddleNode(ListNode *pNode) {ListNode *fastNode = pNode;ListNode *slowNode = pNode;while(fastNode != nullptr && fastNode->next != nullptr) {fastNode = fastNode->next->next;slowNode = slowNode->next;}return slowNode;}
};

4、判断一个链表是否是回文链表

Given a singly linked list, determine if it is a palindrome.Example 1:Input: 1->2
Output: false
Example 2:Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?

分析:依然使用两个指针,fast 和slow指针。

(1)fast 指针每次走两步,slow 指针每次走一步;

(2)fast 指针走到链表末尾的时候,slow 指针走到链表的中间位置结点(链表长度 n 为偶数)或中间位置的前一个结点(链表长度 n 为奇数);

(3)slow 直接到了中间,就可以将整个链表的后半部分压栈实现逆序,依次和前半部分比较即可。

参考代码:

class Solution {
public:bool isPalindrome(ListNode* head) {if(head == nullptr || head->next ==nullptr)return true;ListNode* fast = head->next;ListNode* slow = head;//快慢指针,让慢指针走到中间节点while(fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}if(fast != nullptr) // 偶数节点,让 slow 指向下一个节点slow = slow->next;cut(head, slow);   // 切成两个链表return isEqual(head, reverseNode(slow));}
private:void cut(ListNode* head, ListNode* cutNode) {while(head->next != cutNode) {head = head->next;}head->next = nullptr;}ListNode* reverseNode(ListNode* pHead) {ListNode* pReversedHead = nullptr;ListNode* pCur = pHead;ListNode* pPre = nullptr;while(pCur != nullptr) {ListNode* pNext = pCur->next;//链断开之前一定要保存断开位置后边的结点if(pNext == nullptr) //当next为空时,说明当前结点为尾节点pReversedHead = pCur;pCur->next = pPre;pPre = pCur;pCur = pNext;}return pReversedHead;}bool isEqual(ListNode* L1, ListNode* L2) {while(L1 !=nullptr && L2 != nullptr) {if(L1->val != L2->val)return false;L1 = L1->next;L2 = L2->next;}return true;}
};

5、从有序链表中删除重复节点

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

分析:只需要在遍历时记录当前节点的前节点,然后一旦遇到有重复值的节点就跳过,直到遇到的下一个节点值和当前元素不重复;将记录的前节点的下一个元素指向和当前值不重复的节点。

参考代码:

class Solution4 {
public:ListNode* deleteDuplicates(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;ListNode* current = head;while(current != nullptr && current->next != nullptr) {if(current->next->val == current->val) {//遇到重复节点current->next = current->next->next;} else {current = current->next;}}return head;}
};

6、删除链表的倒数第 n 个节点

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

分析:

这道题目要求我们一次遍历解决问题,那么就得想些比较巧妙的方法了。

比如我们首先要考虑的,如何找到倒数第 N 个节点,由于只允许一次遍历,所以我们不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该删除了。

那么这里还是双指针的思路:首先快指针先向前走 N 步,如果此时快指向空,说明 N 为链表的长度,则需要移除的为首元素,那么此时我们返回 head->next 即可,如果快指针存在,我们再继续往下走,此时慢指针指针也跟着走,直到快指针为最后一个元素时停止,此时慢指针指向要移除元素的前一个元素,我们再修改指针跳过需要移除的元素即可。

参考代码:

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if(head == nullptr|| n == 0)return nullptr;ListNode* fast = head;ListNode* slow = head;while(n--) {if(fast->next != nullptr)fast = fast->next;elsereturn head->next;}while(fast->next != nullptr) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return head;}
};

7、交换链表中的相邻结点

Given 1->2->3->4, you should return the list as 2->1->4->3.

分析:

这道题的话,推荐读者在纸上画画,不然容易晕。细心一些就好。整个过程就是从头开始,对于每一对需要交换的节点,按顺序调整节点的 next 指针,使其指向正确的节点。

参考代码:

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* newHead = new ListNode(0);newHead ->next = head;ListNode* fast = newHead;ListNode* slow;while(fast->next && fast->next->next) {slow = fast->next;fast->next = slow->next;slow->next = slow->next->next;fast->next->next = slow;fast = slow;}return newHead->next;}
};

8、链表元素按奇偶聚集

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

分析:处理偶链表和奇链表的指向,每隔一个元素改变指向即可。

参考代码:

class Solution {
public:ListNode* oddEvenList(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;ListNode* odd = head;//偶链表ListNode* even = head->next;//奇链表ListNode* evenHead = even;//指向奇链表头节点while(even != nullptr && even->next != nullptr) {odd->next = odd->next->next;//偶链表跳着指odd = odd->next;even->next = even->next->next;//奇链表跳着指even = even->next;}odd->next = evenHead;//把偶链表接在奇链表后面return head;}
};

9、链表求和

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

分析:

题目要求:不能修改原始链表。

用容器保存每个节点 val,模拟整数相加即可

参考代码:

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Deque<Integer> stack1 = new LinkedList<>();Deque<Integer> stack2 = new LinkedList<>();while (Objects.nonNull(l1)) {stack1.push(l1.val);l1 = l1.next;}while (Objects.nonNull(l2)) {stack2.push(l2.val);l2 = l2.next;}ListNode dummy = new ListNode(0);int carry = 0;while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {int v1 = stack1.isEmpty() ? 0 : stack1.pop();//移除并返回位于队列尾部的对象int v2 = stack2.isEmpty() ? 0 : stack2.pop();int sum = v1 + v2 + carry;ListNode node = new ListNode(sum % 10);node.next = dummy.next;dummy.next = node;carry = sum / 10;}return dummy.next;}
};

10、分割链表

Example 1:Input: 
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].Example 2:Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

分析:

题目描述:把链表分隔成 k 部分,每部分的长度都应该尽可能相同,排在前面的长度应该大于等于后面的。

我们要知道每个部分结点的个数,才能将整个链表断开成子链表,所以我们首先要统计链表中结点的总个数,然后除以 k,得到的商就是能分成的部分个数,余数就是包含有多余的结点的子链表的个数。

开始 for 循环,循环的结束条件是 i 小于 k 且 root 存在,要生成 k 个子链表,在循环中,先把头结点加入结果 res 中对应的位置,然后就要遍历该子链表的结点个数了。

首先每个子链表都一定包含有 n 个结点,这是之前除法得到的商,然后还要有没有多余结点,如果 i 小于 m,就说明当前子链表还得有一个多余结点,然后将指针向后移动一位,要注意的是,这里的 j 是从 1 开始,因为要移动到子链表的最后一个结点上,而不是移动到下一个子链表的首结点。

新建一个临时结点 t 指向下一个结点,也就是下一个子链表的首结点,然后将链表断开,再将 root 指向临时结点 t,这样就完成了断开链表的操作。

参考代码:

class Solution {
public:vector<ListNode*> splitListToParts(ListNode* root, int k) {vector<ListNode*> res(k);int len = 0;for (ListNode* t = root; t; t = t->next) ++len;int n = len / k, m = len % k;for (int i = 0; i < k && root; ++i) {res[i] = root;for (int j = 1; j < n + (i < m); ++j) {root = root->next;}ListNode* t = root->next;root->next = nullptr;root = t;}return res;}
};

今天的分享就到这里了,希望大家能经常动手写写代码,毕竟纸上得来终觉浅,得知此事要躬行。

如果觉得写得不错,欢迎点好看,转发哦~

推荐阅读

秋招之路-链表面试题集合(一)

碎片化时间真的适合学习吗?

秋招之路-UDP 和 TCP 核心知识总结

认真的人,自带光芒!

原创不易

点个在看呗

这篇关于秋招之路-链表面试题集合(二)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110270

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

Java基础回顾系列-第六天-Java集合

Java基础回顾系列-第六天-Java集合 集合概述数组的弊端集合框架的优点Java集合关系图集合框架体系图java.util.Collection接口 List集合java.util.List接口java.util.ArrayListjava.util.LinkedListjava.util.Vector Set集合java.util.Set接口java.util.HashSetjava

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

【电子通识】半导体工艺——保护晶圆表面的氧化工艺

在文章【电子通识】半导体工艺——晶圆制造中我们讲到晶圆的一些基础术语和晶圆制造主要步骤:制造锭(Ingot)、锭切割(Wafer Slicing)、晶圆表面抛光(Lapping&Polishing)。         那么其实当晶圆暴露在大气中或化学物质中的氧气时就会形成氧化膜。这与铁(Fe)暴露在大气时会氧化生锈是一样的道理。 氧化膜的作用         在半导体晶圆

java集合的概述

集合就是一个容器,我们可以把多个对象放入的容器中。就像水杯(假设容量可以不断扩大)一样,你可以往水杯中不断地添加水,既然是水杯,你就不能往里添加沙子,也就是说集合中添加的对象必须是同一个类型的(引用类型,而不能是基本类型)。 看到集合的介绍会让我们的想起数组,那么集合和数组有什么区别呢? 首先,数组的大小是固定的,而集合理论上大小是不限的。 其次,数组既可以存储基本数据类型的数据,也可以存储

2018秋招C/C++面试题总结

博主从8月中旬开始大大小小面试了十几家公司,至今也许是告一段落吧,希望后面会有好结果,因此总结记录一些C/C++方向常见的问题。和大家一起学习! 参考了互联网的各种资源,自己尝试归类整理,谢谢~ 一、C和C++的区别是什么? C是面向过程的语言,C++是在C语言的基础上开发的一种面向对象编程语言,应用广泛。 C中函数不能进行重载,C++函数可以重载 C++在C的基础上增添类,C是一个结构