赞
踩
笔者投的是嵌入式软件岗,发现手撕代码难度上比软件开发岗是要简单一些的,基本都是leetcode的medeium和easy的水平,基本难的算法不会考,集中在字符串处理和链表,现在把一些常见的链表题做一下。(以下题目均用c++,在类函数里实现)
1.leetcode 21 合并两个有序链表
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
这个题有两种算法,一种是常规算法,一种是递归算法,后者写出来感觉牛逼一点,但是容易出错。
方法一:
- /**
- * 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* l1, ListNode* l2) {
- ListNode *dummy=new ListNode(0);//虚拟头结点不动
- ListNode *cur=dummy;//这个结点是变化的
- if(l1==nullptr)
- return l2;
- if(l2==nullptr)
- return l1;
-
- while(l1!=nullptr&&l2!=nullptr)
- {
- if(l1->val<l2->val)
- {
- cur->next=l1;
- l1=l1->next;
- }
- else
- {
- cur->next=l2;
- l2=l2->next;
- }
-
- cur=cur->next;
- }
-
- if(l1!=nullptr)
- cur->next=l1;
- else
- cur->next=l2;
-
- return dummy->next;
- }
- };
方法2:递归算法
终止条件:当两个链表都为空时,表示我们对链表已合并完成。
如何递归:判断 l1 和 l2 头结点哪个更小,然后较小结点的 next 指针指向其余结点的合并结果。(调用递归)
- class Solution {
- public:
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
-
- if(l1==nullptr)
- return l2;
- if(l2==nullptr)
- return l1;
-
- if(l1->val<=l2->val)
- {
- l1->next=mergeTwoLists(l1->next,l2);//较小结点的next指向其余结点
- return l1;
- }
- else
- {
- l2->next=mergeTwoLists(l1,l2->next);
- return l2
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。