全网营销型网站模版,福州公司网站开发方案,软件或者网站的搜索怎么做,百度seo如何快速排名Problem: 21. 合并两个有序链表 文章目录 思路1 递归实现2 迭代实现 Code 思路 方法1 递归实现 方法2 迭代实现 1 递归实现
分析问题 对于本题#xff0c;合并两个有序链表A和B#xff0c;mergeTwoLists#xff08;A,B#xff09;#xff0c;递归只需要关注本层我要干什么… Problem: 21. 合并两个有序链表 文章目录 思路1 递归实现2 迭代实现 Code 思路 方法1 递归实现 方法2 迭代实现 1 递归实现
分析问题 对于本题合并两个有序链表A和BmergeTwoListsA,B递归只需要关注本层我要干什么返回什么首先我要先直到AB 哪个链表的头最小让最小的那个节点指向剩余部分合并的有序链表头然后返回当前的结点头。 基本情况
当A为空的时候直接返回B因为这意味着B所有的结点都大于A的所有结点。当B为空的时候直接返回A同理。
class Solution {
public:// 递归实现ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 nullptr ) return list2 ; if(list2 nullptr ) return list1 ; if(list1-val list2-val) {list1-next mergeTwoLists(list1-next,list2) ; return list1 ; }else {list2-next mergeTwoLists(list1 , list2-next) ; return list2 ; }}
};2 迭代实现
创建一个新的节点preHead 遍历两个链表每次让新节点指向两个链表中的最小的一个结点更新 preHead。
Code
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {// 创建一个新节点ListNode* preHead new ListNode(-1);ListNode* prev preHead;while(l1 l2 ) {if(l1-val l2-val ) {prev-next l1 ; l1 l1-next ; }else {prev-next l2 ; l2 l2-next ; }prev prev-next ; }if(l1 nullptr ) {prev-next l2 ; }else {prev-next l1 ; }preHead preHead-next ; return preHead ; }};
