网站建设 微信开发,网站订票策划方案,做安利能开个人网站,写代码做网站#xff08;一#xff09;找出链表的环的入口结点 JZ23 链表中环的入口结点 中等 通过率#xff1a;36.78% 时间限制#xff1a;1秒 空间限制#xff1a;64M 知识点链表哈希双指针 描述 给一个长度为n链表#xff0c;若其中包含环#xff0c;请找出该链表的环的入口结点…一找出链表的环的入口结点 JZ23 链表中环的入口结点 中等 通过率36.78% 时间限制1秒 空间限制64M 知识点链表哈希双指针 描述 给一个长度为n链表若其中包含环请找出该链表的环的入口结点否则返回null。
数据范围 n≤100001结点值10000 要求空间复杂度 O(1)时间复杂度 O(n)
例如输入{1,2},{3,4,5}时对应的环形链表如下图所示
可以看到环的入口结点的结点值为3所以返回结点值为3的结点。 输入描述 输入分为2段第一段是入环前的链表部分第二段是链表环的部分后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表 返回值描述 返回链表的环的入口结点即可我们后台程序会打印这个结点对应的结点值若没有则返回对应编程语言的空结点即可。 示例1 输入 {1,2},{3,4,5} 返回值 3 说明 返回环形链表入口结点我们后台程序会打印该环形链表入口结点对应的结点值即3 示例2 输入 {1},{} 返回值 “null” 说明 没有环返回对应编程语言的空结点后台程序会打印null 示例3 输入 {},{2}
返回值 2 说明 环的部分只有一个结点所以返回该环形链表入口结点后台程序打印该结点对应的结点值即2
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {if (pHead NULL || pHead-next NULL || pHead-next-next NULL) {return NULL;}ListNode* slow pHead-next;ListNode* fast pHead-next-next;while (slow ! fast) {slow slow-next;if (fast NULL || fast-next NULL || fast-next-next NULL) {return NULL;}fast fast-next-next;}slow pHead;while (slow ! fast) {slow slow-next;fast fast-next;}return slow;}
};二判断链表是否有环 leetcode 141 141. 环形链表 难度简单 给定一个链表判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 如果链表中存在环则返回 true 。 否则返回 false 。
进阶 你能用 O(1)即常量内存解决此问题吗
示例 1
输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。
示例 2
输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。
示例 3
输入head [1], pos -1 输出false 解释链表中没有环。
提示 链表中节点的数目范围是 [0, 104] -105 Node.val 105 pos 为 -1 或者链表中的一个 有效索引 。 通过次数391,460 提交次数769,105
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {
public:bool hasCycle(ListNode *head) {if (head NULL || head-next NULL || head-next-next NULL) {return false;}ListNode* slow head-next;ListNode* fast head-next-next;while (slow ! fast) {slow slow-next;if (fast NULL || fast-next NULL || fast-next-next NULL) {return false;}fast fast-next-next;}return true;}一重复的结点不保留 JZ76 删除链表中重复的结点 中等 通过率22.07% 时间限制1秒 空间限制64M 知识点链表 描述 在一个排序的链表中存在重复的结点请删除该链表中重复的结点重复的结点不保留返回链表头指针。 例如链表 1-2-3-3-4-4-5 处理后为 1-2-5
数据范围链表长度满足 0≤n≤1000 链表中的值满足 1≤val≤1000
进阶空间复杂度 O(n) 时间复杂度 O(n)
例如输入{1,2,3,3,4,4,5}时对应的输出为{1,2,5}对应的输入输出链表如下图所示
示例1 输入 {1,2,3,3,4,4,5} 返回值 {1,2,5} 示例2 输入 {1,1,1,8} 返回值 {8} 自己答案
方法使用unordered_mapint, int mm 和 创建头结点
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if (pHead NULL) {return NULL;}std::unordered_mapint, int m;ListNode* cur pHead;while (cur ! NULL) {m[cur-val];cur cur-next;}ListNode* res new ListNode(0);res-next pHead;cur res;while (cur-next ! NULL) {if (m[cur-next-val] ! 1) {cur-next cur-next-next;} else {cur cur-next;}}return res-next;}
};二重复的结点保留一个 Leetcode 83 83. 删除排序链表中的重复元素 难度简单 存在一个按升序排列的链表给你这个链表的头节点 head 请你删除所有重复的元素使每个元素 只出现一次 。 返回同样按升序排列的结果链表。
示例 1
输入head [1,1,2] 输出[1,2]
示例 2
输入head [1,1,2,3,3] 输出[1,2,3]
提示 链表中节点数目在范围 [0, 300] 内 -100 Node.val 100 题目数据保证链表已经按升序排列 通过次数271,350 提交次数504,656 请问您在哪类招聘中遇到此题
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* cur head;ListNode* nex head;while(nex ! NULL){nex nex-next;if(nex NULL) {return head;}if(cur-val nex-val) {cur-next nex-next;} else {cur cur-next;} }return head;}
};JZ18 删除链表的节点 简单 通过率60.23% 时间限制1秒 空间限制256M 知识点链表 描述 给定单向链表的头指针和一个要删除的节点的值定义一个函数删除该节点。返回删除后的链表的头节点。 1.此题对比原题有改动 2.题目保证链表中节点的值互不相同 3.该题只会输出返回的链表和结果做对比所以若使用 C 或 C 语言你不需要 free 或 delete 被删除的节点
数据范围: 0链表节点值10000 0链表长度10000 示例1 输入 {2,5,1,9},5 返回值 {2,1,9}
说明 给定你链表中值为 5 的第二个节点那么在调用了你的函数之后该链表应变为 2 - 1 - 9 示例2 输入 {2,5,1,9},1 返回值 {2,5,9}
说明 给定你链表中值为 1 的第三个节点那么在调用了你的函数之后该链表应变为 2 - 5 - 9
方法pcur 指向最后一个结点
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * param val int整型 * return ListNode类*/ListNode* deleteNode(ListNode* head, int val) {// write code hereif (head NULL) {return NULL;}//为了解决第一个节点被删除的问题新增一个头节点ListNode* res new ListNode(0);res-next head;ListNode* cur res;while (cur-next ! NULL) {if (cur-next-val val) {cur-next cur-next-next;} else {cur cur-next;}}return res-next;}
};JZ35 复杂链表的复制 较难 通过率23.47% 时间限制1秒 空间限制64M 知识点链表 描述 输入一个复杂链表每个节点中有节点值以及两个指针一个指向下一个节点另一个特殊指针random指向一个随机节点请对此链表进行深拷贝并返回拷贝后的头结点。注意输出结果中请不要返回参数中的节点引用否则判题程序会直接返回空。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针虚线箭头表示random指针。为简单起见指向null的指针没有画出。
示例: 输入:{1,2,3,4,5,3,5,#,2,#} 输出:{1,2,3,4,5,3,5,#,2,#} 解析:我们将链表分为两段前半部分{1,2,3,4,5}为ListNode后半部分{3,5,#,2,#}是随机指针域表示。 以上示例前半部分可以表示链表为的ListNode:1-2-3-4-5 后半部分35#2#分别的表示为 1的位置指向32的位置指向53的位置指向null4的位置指向25的位置指向null 如下图:
示例1 输入 {1,2,3,4,5,3,5,#,2,#} 返回值 {1,2,3,4,5,3,5,#,2,#}
方法复制节点放在下一个位置
/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/class Solution {public:RandomListNode* Clone(RandomListNode* pHead) {//空节点直接返回if (pHead NULL)return pHead;//第一步使用单指针遍历链表对每个节点新建一个拷贝节点并插入到该节点之后。//原始节点RandomListNode* cur pHead;//遍历原始链表开始复制while (cur ! NULL) {//拷贝节点RandomListNode* clone new RandomListNode(cur-label);//将拷贝节点插入到原始节点后面clone-next cur-next;cur-next clone;cur clone-next;}//第二步使用双指针遍历链表两个指针每次都移动两步//拷贝节点的随机指针 调整为 指向节点的下一个节点。//原始节点 cur pHead;//拷贝节点RandomListNode* clone pHead-next;//返回结果RandomListNode* res pHead-next;//连接新链表的random节点while (cur ! NULL) {//跟随前一个连接randomif (cur-random NULL)clone-random NULL;else//后一个节点才是拷贝的clone-random cur-random-next;//cur-next必定不为空cur cur-next-next;//检查末尾节点if (clone-next ! NULL)clone clone-next-next;}//第三步使用双指针再次遍历链表两个指针每次都移动一步//原始节点和拷贝节点的next指针 都调整为 指向节点的下一个节点。cur pHead;clone pHead-next;while (cur ! NULL) {cur-next cur-next-next;//检查末尾节点if (clone-next ! NULL) {clone-next clone-next-next;}cur cur-next;clone clone-next;}return res;}
};JZ25 合并两个排序的链表 描述 输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围 0≤n≤1000−1000≤节点值≤1000 要求空间复杂度 O(1)时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时合并后的链表为{1,2,3,4,5,6}所以对应的输出为{1,2,3,4,5,6}转换过程如下图所示
或输入{-1,2,4},{1,3,4}时合并后的链表为{-1,1,2,3,4,4}所以对应的输出为{-1,1,2,3,4,4}转换过程如下图所示
示例1 输入 {1,3,5},{2,4,6} 返回值 {1,2,3,4,5,6} 示例2 输入 {},{} 返回值 {} 示例3 输入 {-1,2,4},{1,3,4} 返回值 {-1,1,2,3,4,4}
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if (pHead1 NULL pHead2 NULL) {return NULL;}if (pHead1 NULL pHead2 ! NULL) {return pHead2;}if (pHead1 ! NULL pHead2 NULL) {return pHead1;}if (pHead1-val pHead2-val) {pHead1-next Merge(pHead1-next, pHead2);return pHead1;} else {pHead2-next Merge(pHead1, pHead2-next);return pHead2;}}
};JZ52 两个链表的第一个公共结点 简单 通过率38.04% 时间限制1秒 空间限制64M 知识点链表 描述 输入两个无环的单向链表找出它们的第一个公共结点如果没有公共节点则返回空。注意因为传入数据是链表所以错误测试数据的提示是用其他方式显示的保证传入数据是正确的
数据范围 n≤1000 要求空间复杂度 O(1)时间复杂度 O(n)
例如输入{1,2,3},{4,5},{6,7}时两个无环的单向链表的结构如下图所示
可以看到它们的第一个公共结点的结点值为6所以返回结点值为6的结点。 输入描述 输入分为是3段第一段是第一个链表的非公共部分第二段是第二个链表的非公共部分第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面用户得到的输入只有pHead1和pHead2。 返回值描述 返回传入的pHead1和pHead2的第一个公共结点后台会打印以该节点为头节点的链表。 示例1 输入 {1,2,3},{4,5},{6,7} 返回值 {6,7} 说明 第一个参数{1,2,3}代表是第一个链表非公共部分第二个参数{4,5}代表是第二个链表非公共部分最后的{6,7}表示的是2个链表的公共部分 这3个参数最后在后台会组装成为2个两个无环的单链表且是有公共节点的 示例2 输入 {1},{2,3},{} 返回值 {} 说明 2个链表没有公共节点 ,返回null后台打印{}
方法交叉遍历法
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {ListNode* head1 pHead1;ListNode* head2 pHead2;while (head1 ! head2) {head1 (head1 NULL ? pHead2 : head1-next);head2 (head2 NULL ? pHead1 : head2-next);}return head1;}
};JZ22 链表中倒数最后k个结点 简单 通过率39.15% 时间限制1秒 空间限制256M 知识点链表 描述 输入一个长度为 n 的链表设链表中的元素的值为 ai 返回该链表中倒数第k个节点。 如果该链表长度小于k请返回一个长度为 0 的链表。
数据范围0≤n≤1050≤ai≤1090≤k≤109 要求空间复杂度 O(n)时间复杂度 O(n) 进阶空间复杂度 O(1)时间复杂度 O(n)
例如输入{1,2,3,4,5},2时对应的链表结构如下图所示
其中蓝色部分为该链表的最后2个结点所以返回倒数第2个结点也即结点值为4的结点即可系统会打印后面所有的节点来比较。 示例1 输入 {1,2,3,4,5},2 返回值 {4,5} 说明 返回倒数第2个节点4系统会打印后面所有的节点来比较。 示例2 输入 {2},8 返回值 {}
方法head指针使用for循环head指针 走到 最后一个节点
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pHead ListNode类 * param k int整型 * return ListNode类*/ListNode* FindKthToTail(ListNode* pHead, int k) {// write code hereif (pHead NULL || k 0) {return NULL;}ListNode* head pHead;ListNode* tail pHead;for (int i 0; i k-1; i) {if (head-next ! NULL) {head head-next;} else {return NULL;}}while (head-next ! NULL) {head head-next;tail tail-next;}return tail;}
};JZ6 从尾到头打印链表 简单 通过率28.84% 时间限制1秒 空间限制64M 知识点链表 描述 输入一个链表的头节点按链表从尾到头的顺序返回每个节点的值用数组返回。
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]
0 链表长度 10000 示例1 输入 {1,2,3} 返回值 [3,2,1] 示例2 输入 {67,0,24,58} 返回值 [58,24,0,67] 自己答案
方法栈
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {std::vectorint vec;if (head NULL) {return vec;}std::stackint sta;while (head ! NULL) {sta.push(head-val);head head-next;}while (!sta.empty()) {vec.push_back(sta.top());sta.pop();}return vec;}
};JZ24 反转链表 简单 通过率38.82% 时间限制1秒 空间限制64M 知识点链表 描述 给定一个单链表的头结点pHead(该头节点是有值的比如在下图它的val是1)长度为n反转该链表后返回新链表的表头。
数据范围 0≤n≤1000 要求空间复杂度 O(1) 时间复杂度 O(n) 。
如当输入链表{1,2,3}时 经反转后原链表变为{3,2,1}所以对应的输出为{3,2,1}。 以上转换过程如下图所示
示例1 输入 {1,2,3} 返回值 {3,2,1} 示例2 输入 {} 返回值 {} 说明 空链表则输出空
第一个方法栈
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {if (pHead NULL) {return NULL;}std::stackListNode* sta;while (pHead ! NULL) {sta.push(pHead);pHead pHead-next;}ListNode* res sta.top();ListNode* cur sta.top();sta.pop();while (!sta.empty()) {cur-next sta.top();sta.pop();cur cur-next;}cur-next NULL;return res;}
};第二个方法数组
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/class Solution {
public:ListNode* ReverseList(ListNode* pHead) {if (pHead NULL) {return NULL;}std::vectorListNode* vec;while (pHead ! NULL) {vec.push_back(pHead);pHead pHead-next;}reverse(vec.begin(), vec.end());ListNode* res vec[0];ListNode* cur vec[0];for (int i 1; i vec.size(); i) {cur-next vec[i];cur cur-next;}cur-next NULL;return res;}
};
