標(biāo)簽： C++ 算法 LeetCode 鏈表

每日算法——leetcode系列

問(wèn)題 Merge Two Sorted Lists

Difficulty: Easy

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
    }
};

翻譯

合并兩個(gè)有序鏈表

難度系數(shù)：簡(jiǎn)單

合并兩個(gè)有序鏈表并返回一個(gè)新鏈表。新的鏈表的由兩個(gè)有序的鏈表的節(jié)點(diǎn)組成倔叼。

思路

兩種思考方式：

• 先定一個(gè)主鏈表萌踱，把另一個(gè)鏈表合并到這個(gè)主鏈表
  假定一個(gè)鏈表dummy, 為方便遍歷卸夕，設(shè)dummy的初始值為-1蒂培，next指向l1(主鏈表)搀缠，為返回值缰泡，還得新那家一個(gè)鏈表tempLink = dummy

• 如果l1的值比l2小烧颖，templink = l1, 再遍歷l1->next

• 如果l1的值比l2大弱左，則把temlink->next = l2, tempLink = tempLink->next, 再把tempLink批回主鏈表， 這樣到最后有可能副鏈表還不為空炕淮，再加到后面就好

• 直接同時(shí)遍歷兩個(gè)鏈表拆火，再每次取其中小的
  這種思路比較直接，就是同時(shí)遍歷兩個(gè)鏈表涂圆， 哪個(gè)小用哪個(gè)们镜， 再把剩下的放到最后

代碼

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *p1 = l1,  *p2=l2;
        ListNode dummy(-1);
        dummy.next = p1;
        ListNode *tempLink = &dummy;
        
        while(p1 != nullptr && p2 != nullptr) {
            if (p1->val < p2->val) {
                tempLink = p1;
                p1 = p1->next;
            } else {
                tempLink->next = p2;
                p2 = p2->next;
                tempLink = tempLink->next;
                tempLink->next = p1;
            }
        }
        if (p2 != nullptr) {
            tempLink->next = p2;
        }
        
        return dummy.next;
    }
    
    ListNode* mergeTwoLists2(ListNode* l1, ListNode* l2) {
        ListNode *p1 = l1,  *p2=l2;
        ListNode dummy(-1);
        dummy.next = nullptr;
        ListNode *tempLink = &dummy;
        
         while(p1 != nullptr && p2 != nullptr) {
            if (p1->val < p2->val) {
                tempLink->next = p1;
                p1 = p1->next;
                tempLink = tempLink->next;
            } else {
                tempLink->next = p2;
                p2 = p2->next;
                tempLink = tempLink->next;
            }
        }
        if (p2 != nullptr) {
            tempLink->next = p2;
        } else if ( p1 != nullptr) {
            tempLink->next = p1;
        }
        
        return dummy.next;
    }

};