网站排名在哪里优化,徐州网站建设推广,手机网站怎么放到桌面上,深圳美容网站建设题目汇总 Leetcode 21, 82, 160, 206, 237, 268 Leetcode 21. 合并两个有序链表
归并排序的思路#xff0c;创建一个哨兵节点从两个链表中按大小插入即可。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(…题目汇总 Leetcode 21, 82, 160, 206, 237, 268 Leetcode 21. 合并两个有序链表
归并排序的思路创建一个哨兵节点从两个链表中按大小插入即可。
/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dum new ListNode(-1);ListNode* curr dum;while(list1 list2) {if (list1-val list2-val) {curr-next list1;list1 list1-next;} else {curr-next list2;list2 list2-next;}curr curr-next;}while(list1) {curr-next list1;curr curr-next;list1 list1-next;}while(list2) {curr-next list2;curr curr-next;list2 list2-next;}return dum-next;}
};时间复杂度 O ( N M ) \mathcal{O}(NM) O(NM) 空间复杂度 O ( 1 ) \mathcal{O}(1) O(1)
Leetcode.82 Linkedlist中删除所有重复片段
这道题目要求是删除所有重复的片段而不仅仅是去重基本思路就是线性扫描如果扫描的片段有重复也就是长度大于1那么就跳过这部分接着找下面如果查看部分长度1那么就将该元素加入结果。在循环时维持一个循环不变量 建立一个pred节点这个节点在每一个循环开始时一定指向的是当前最新的不重复节点位置 class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* dum new ListNode(-1);dum-next head;auto pred dum; // 哨兵节点作为第一个不会重复的节点while(pred-next) {/*循环不变量 -pred前驱节点时刻定位*/auto p1 pred-next;while(p1 pred-next-valp1-val) {p1 p1-next;}//确定是不是要更新pred到新的不重复if (pred-next-nextp1) pred pred-next; //遇到新的不重复节点更新pred的位置else pred-next p1; // 跳过当前重复片段pred指向下一个片段开始位置但这里不更新pred位置因为当前p1位置可能重复需要下一个循环进行检测.}return dum-next;}
};时间复杂度 O ( N ) \mathcal{O}(N) O(N) 空间复杂度 O ( 1 ) \mathcal{O}(1) O(1)
Leetcode 206. 反转一个单向链表
要求in-place反转基本思路可以进行递归反转在每一次递归中把下一层返回节点的next指向当前节点即可。 第二种方法是利用迭代的方式每一次循环中保存当前节点的下一个节点nxt并把当前节点next连接前一个节点prev然后更新prev为当前节点然后继续遍历。
//递归解法
class Solution {
public:ListNode* ans new ListNode(-1);ListNode* reverseList(ListNode* head) {dfs(head);return ans-next;}ListNode* dfs(ListNode* head) {if(!head || !head-next) {//保存反转头节点ans-next head;return head;} ListNode* res dfs(head-next);//反转当前节点res-next head;//断开当前节点与next节点连接res-next-next nullptr;//返回当前节点return res-next;}
};//迭代解法
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev NULL;while(head) {ListNode* curr head;head head-next;curr-next prev;prev curr;}return prev;}
};
时间复杂度递归、迭代都是 O ( N ) \mathcal{O}(N) O(N) 空间复杂度递归 O ( N ) \mathcal{O}(N) O(N) 栈的深度。迭代 O ( 1 ) \mathcal{O}(1) O(1)
