天津北辰做网站,怎样做网站优化 知乎,做私单的网站,wordpress分只显示标题来源#xff1a;左程云算法
链表的题目我们经常是有思路但是实现起来总有些小问题#xff0c;所以是准备笔试应多加练习的一类题
206. 反转链表
这道题我们可以新开链表来存#xff0c;但是如果面试中有这道题#xff0c;面试官让你优化又该如何呢#xff1f;所以我们采…来源左程云算法
链表的题目我们经常是有思路但是实现起来总有些小问题所以是准备笔试应多加练习的一类题
206. 反转链表
这道题我们可以新开链表来存但是如果面试中有这道题面试官让你优化又该如何呢所以我们采用前后指针方法来解决
/*** 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* reverseList(ListNode* head) {ListNode *prenullptr;//前指针ListNode *nextnullptr;//后指针while(head){ nexthead-next;//先把该节点的下一个结点存下来head-nextpre;//修改该结点的下一个结点为前一结点prehead;//前一结点移到当前位置headnext;//当前结点往后移动}return pre;//最后pre保存新的头结点另两个结点为空}
};
同时本题还有递归解法非常巧妙
/*** 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* reverseList(ListNode* head) {if(headnullptr||head-nextnullptr)return head;//第一个条件只是判断初始链表为空的情况ListNode *curreverseList(head-next);//以[1,2,3,4,5]为例现在head指向4cur指向5head-next-nexthead;//head-next指向反转链表的最后一个此句把自己接到后面head-nextnullptr;//接到的是尾部所以next为nullptrreturn cur;}
};
附录反转双链表
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre nullptr;ListNode* next nullptr;while (head ) {next head-next;head-next pre;head-last next;pre head;head next;}return pre;}
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 head{};//哨兵结点ListNode* curhead;//指向哨兵结点while(list1list2){if(list1-vallist2-val){cur-nextlist1;//指向小的list1list1-next;//链表指针移动}else{cur-nextlist2;list2list2-next;}curcur-next;//合并链表指针移动到尾结点}cur-nextlist1?list1:list2;//哪个有剩余就加上return head.next;//返回头节点}
};
2. 两数相加
这道题依然使用哨兵结点便于处理
/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {int up 0;//算进位和余数ListNode* head new ListNode;//哨兵结点ListNode* cur head;//指针指向哨兵结点while (l1 || l2 || up) {//只要链表没遍历完或进位里仍有数int val1 l1 ? l1-val : 0;//链表不为空取值int val2 l2 ? l2-val : 0;up val1 val2;//之前进上的位与当前相加ListNode* t new ListNode(up % 10);//新建结点存答案up / 10;//应进位多少cur-next t;//接到答案链表后面cur cur-next;//链表指针移动if (l1)l1 l1-next; //链表不为空移动if (l2)l2 l2-next;}return head-next;//返回哨兵结点保存的头结点}
};
86. 分隔链表
这个题如果我们扫描然后把小的放前面用到的指针比较多较麻烦。
所以我们用两个链表分别存储再最后合并即可。
/*** 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* partition(ListNode* head, int x) {//开两个链表分别存储最后合并链表即可ListNode* lower new ListNode(0);//x的结点ListNode* upper new ListNode(0);//x的结点//两个都是哨兵结点ListNode *p1 lower, *p2 upper;//指针分别指向两链表便于后续增加结点if (!head)return head;//为空直接返回while (head) {//一直遍历if (head-val x) {//小于接到lower链表p1-next head;p1 p1-next;head head-next;} else {p2-next head;//大于等于接到upper链表p2 p2-next;head head-next;}}p1-next upper-next;//upper接到lower后面p2-next nullptr;//尾部置nullreturn lower-next;}
};
