leetcode 21

递归的方式

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1 == nullptr){return l2;}else if(l2 == nullptr){return l1;}else if(l1->val < l2->val){l1->next = mergeTwoLists(l1->next, l2);return l1;}else if(l1->val > l2->val){l2->next = mergeTwoLists(l1, l2->next);return l2;}else{l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

递归调用顺序是

m(1,1) -> m(1,3) -> m(2,3) -> m(4,3) ->m(4,4) -> m(4, nullptr)

比较特殊的是相等的情况；
这道题用递归做还是挺有创意的，一边递归，一边修改指针的内容；

迭代的方式

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* pre = new ListNode();ListNode* res = pre; while(l1 !=nullptr && l2!= nullptr){if(l1->val < l2->val){pre->next = l1;l1 = l1->next;}else{pre->next = l2;l2 = l2->next;}pre = pre->next;}pre ->next = l1 == nullptr? l2:l1;return res->next;}
};

迭代的方式空间复杂度会比递归好