非递归方法:
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == nullptr) return l2; if(l2 == nullptr) return l1; ListNode* pHead = nullptr; if(l1->val < l2->val) pHead = l1, l1 = l1->next; else pHead = l2, l2 = l2->next; ListNode* pTail = pHead; while(l1 != nullptr && l2 != nullptr) { if(l1->val < l2->val) pTail->next = l1, l1 = l1->next; else pTail->next = l2, l2 = l2->next; pTail = pTail->next; } if(l1 == nullptr) pTail->next = l2; else pTail->next = l1; return pHead; } };
递归方法:
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1) return l2; if(!l2) return l1; if(l1->val<=l2->val) { l1->next = mergeTwoLists(l1->next,l2); return l1; } else { l2->next = mergeTwoLists(l1,l2->next); return l2; } } };