网站内容规划,厦门在哪个网站做用工报备,龙岩做网站价格,上海大良网站建设力扣刷题 1. 反转链表#xff08;206#xff09;1.1 题目描述1.2 题目分析1.2.1 头插法1.2.2 箭头反转 1.3 题目代码1.3.1 头插入1.3.2 箭头反转 2.合并两个有序链表#xff08;21#xff09;2.1 题目描述2.2 题目分析2.3 题目代码 1. 反转链表#xff08;206#xff09;… 力扣刷题 1. 反转链表2061.1 题目描述1.2 题目分析1.2.1 头插法1.2.2 箭头反转 1.3 题目代码1.3.1 头插入1.3.2 箭头反转 2.合并两个有序链表212.1 题目描述2.2 题目分析2.3 题目代码 1. 反转链表206
1.1 题目描述 1.2 题目分析
1.2.1 头插法
要将原来的链表进行反转很容易想到将原来的节点取下来然后一个一个进行头插到新链表中struct ListNode* newheadNULL。 原链表中如果cur不为空那么cur-nextnewhead,再将newhead置为新链表的头节点。 为了方便记录原链表节点的位置在原链表上定义一个struct ListNode* nextcur-next。
如果cur为空这里就需要一个新的链表所以最后不要忘记返回新链表的头节点。
1.2.2 箭头反转
还有一种方法就是将这些节点的箭头反向也就是将后一个节点的next等于前一个节点。 反转之后就是这样: 也就是说先定义两个指针先将n1置为空然后n2指向头节点再将n2-nextn1。然后继续往后走需要记录n2后一个节点位置再定义一个n3head-next,只要链表不为空就让 n2-nextn1;n1n2;n2n3。 但是在最后一步n3可能为空所以得加一个判断为空就不往后执行了。 最值得注意的一点是如果原链表为空那么后面都不执行所以开始得加一个判断 if(headNULL){return NULL;}1.3 题目代码
1.3.1 头插入
struct ListNode* reverseList(struct ListNode* head){struct ListNode* curhead;struct ListNode* newheadNULL;while(cur){struct ListNode* nextcur-next;cur-nextnewhead;newheadcur;curnext;}return newhead;
}1.3.2 箭头反转
struct ListNode* reverseList(struct ListNode* head){if(headNULL){return NULL;}struct ListNode* n1,*n2,*n3;n1NULL;n2head;n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3){n3n3-next;}}return n1;
}2.合并两个有序链表21
2.1 题目描述 2.2 题目分析
题目要求是按照升序返回合并的原来排好序的两个链表这里就可以用尾插比较两个链表节点的val对比一下取小的进行尾插。
这里肯定要事先判断一下这两个链表是不是为空如果链表1为空就直接返回链表2。同样链表2为空就返回链表1。 if(list1NULL){return list2;}if(list2NULL){return list1;}在已有的链表上面经行插入比较繁琐就直接用一个新的最后返回排好链表的头节点就行。 只有两个链表都不为空时再考虑是链表1节点的val与链表2的val如果 list1-val list2-val还是得判断一下这个新链表里面有没有节点没有就直接让headtaillist1有就实现尾插。 if(tailNULL){headtaillist1;}else{tail-nextlist1;tailtail-next;}然后链表1继续往后走。 但是如果 list1-val list2-val是错误的那么链表2也是同样的 if (tail NULL){head tail list2;}else{tail-next list2;tail tail-next;}list2 list2-next;当一个链表已经排好了如果剩下的是链表1就直接插入 if(list1){tail-nextlist1;}如果剩下的是链表2就直接插入 if(list2){tail-nextlist2;}最后别忘记返回头节点。
2.3 题目代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1NULL){return list2;}if(list2NULL){return list1;}struct ListNode* headNULL;struct ListNode* tailNULL;while(list1list2){if(list1-vallist2-val){if(tailNULL){headtaillist1;}else{tail-nextlist1;tailtail-next;}list1list1-next;}else{if(tailNULL){headtaillist2;}else{tail-nextlist2;tailtail-next;}list2list2-next;}}if(list1){tail-nextlist1;}if(list2){tail-nextlist2;}return head;}
