设计网站100个免费,网站建设与管理课后作业答案,免费优化网站的软件,优化标题关键词技巧题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 比如以下例子#xff1a; 题目接口#xff1a;
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListN… 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 比如以下例子 题目接口
/*** 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) {}
};
题目解答
1.迭代法尾插法 这个题目其实我之前做过。只不之前用的是迭代法来做的。迭代法的解题代码如下 class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 nullptr){return list2;}if(list2 nullptr){return list1;}ListNode* head nullptr;//指向头节点ListNode* tail nullptr;//指向尾节点while(list1list2){if(list1-vallist2-val){if(head nullptr){head tail list1;}else{tail-next list1;tail tail-next;}list1 list1-next;tail-next nullptr;}else{if(head nullptr){head tail list2;}else{tail-next list2;tail tail-next;}list2 list2-next;tail-next nullptr;}}//若list1或者list2里边有未清空的便直接插入if(list1){tail-next list1;}if(list2){tail-next list2;}return head;}
}; 看起来特别长是吧是的没错。并且这里还有许多细节要注意。 1.tail表示的是链表的尾节点所以在尾插了一个节点以后要向后移动来保证tail所在位置依旧是链表尾。 2.tail在插入一个节点以后要在list1或者list2找到下一个节点后置空。 有一说一迭代法是真的麻烦。 2.递归写法 首先依照递归法的使用步骤。首先就要先找到重复的子问题。其实非常简单。 1.重复的子问题就是找到两个链表中小的尾插。 2.递归的结束条件当两个链表有一个空的时候便结束递归返回不为空的链表。 3.函数体的写法找到小的插入到链表中。首先便要找到两个链表中比较小的数然后搞一个新的节点这个节点的值便是这个小的值。 class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 nullptr){return list2;}if(list2 nullptr){return list1;}if(list1-vallist2-val)//确定头节点后一直找剩下的链表的值中较小的尾插{list1-next mergeTwoLists(list1-next,list2);return list1;}else{list2-next mergeTwoLists(list1,list2-next);return list2;}}
}; 递归的写法可比迭代的写法简单多了。不过递归写法的代码不是那么好想出来的。得多多练习才行。
