題意為將兩個(gè)已經(jīng)排好序的鏈表合并為一個(gè)新的有序鏈表 可以用遞歸和非遞歸兩種方法解決問題：
（1）非遞歸
首先需要?jiǎng)?chuàng)建一個(gè)新的鏈表，然后依次遍歷兩個(gè)鏈表，并將兩個(gè)數(shù)組中較小的元素依次插入新鏈表中。 值得注意的是，若一個(gè)鏈表為空或已經(jīng)遍歷完全，則將另一個(gè)鏈表插入即可
class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *head = new ListNode(-1); ListNode *p1 = l1; ListNode *p2 = l2; ListNode *curNode = head; while(p1 && p2) { if( p1->val < p2->val ) { curNode->next = p1; curNode = curNode->next; p1 = p1->next; } else if(p2->val < p1->val ) { curNode->next = p2; curNode = curNode->next; p2 = p2->next; } else { curNode->next = p1; curNode = curNode->next; p1 = p1->next; curNode->next = p2; curNode = curNode->next; p2 = p2->next; } } if(p1) { curNode->next = p1; } if(p2) { curNode->next = p2; } return head->next; }};（2）遞歸
考慮，若鏈表 l1 為空，則返回 l2 鏈表；若 l2 鏈表為空，則返回 l1 鏈表 若兩鏈表均非空，則比較鏈表 l1 和 l2 的第一個(gè)元素，若 l1 較小，則繼續(xù)比較 l1->next 和 l2 的第一個(gè)元素大小，并返回 l1
class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == NULL) { return l2; } if(l2 == NULL) { return l1; } if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next,l2); return l1; } if(l2->val <= l1->val) { l2->next = mergeTwoLists(l1,l2->next); return l2; } }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
