21. Merge Two Sorted Lists leetcode(lists)

Merge Two Sorted Lists

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.

方法一、遞歸的方法

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if(l1 == NULL) return l2;
    else if(l2 == NULL) return l1;
    ListNode *pNewHead = NULL;
    if(l1->val < l2->val){
        pNewHead = l1;
        pNewHead->next = mergeTwoLists(l1->next,l2);
    }
    else {
        pNewHead = l2;
        pNewHead->next = mergeTwoLists(l1,l2->next);
    }

    return pNewHead;
}
           

方法二、多開辟了一個連結清單

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(NULL == l1 || NULL == l2)
        {
            return (NULL==l1)?l2:l1;
        }

        ListNode l3(); //必須使用這種定義，如果寫成ListNode* l3會逾時，必須帶頭節點
        ListNode* p1;
        ListNode* p2;
        ListNode* p3;

        p1 = l1;
        p2 = l2;
        p3 = &l3;

        while(p1 && p2)
        {
            ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
            if(p1->val <= p2->val)
            {
                cout<<"1p1 "<<p1->val<<endl;
                tmp->val = p1->val;
                tmp->next = NULL;
                p1 = p1->next;
            }
            else
            {
                cout<<"1p2 "<<p2->val<<endl;
                tmp->val = p2->val;
                tmp->next = NULL;
                p2 = p2->next;
            }

            p3->next = tmp;
            p3 = tmp;
        }

        while(p1)
        {
            cout<<"2p1"<<p1->val<<endl;
            ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
            tmp->val = p1->val;
            tmp->next = NULL;
            p3->next = tmp;
            p3 = tmp;
            p1 = p1->next;
        }

        while(p2)
        {
            cout<<"2p2"<<p2->val<<endl;
            ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
            tmp->val = p2->val;
            tmp->next = NULL;
            p3->next = tmp;
            p3 = tmp;
            p2 = p2->next;
        }

        return l3.next; //因為帶頭節點是以必須傳回l3.next
    }
           

方法三、直接在第一個連結清單上進行修改，最終傳回第一個連結清單

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(NULL == l1 || NULL == l2)
        {
            return (NULL==l1)?l2:l1;
        }

        ListNode* p1= l1;
        ListNode* pre = p1;
        ListNode* p2 = l2;
        while(p1 && p2)
        {
            ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
            if(p1->val <= p2->val)
            {
                pre = p1;
                p1 = p1->next;
            }
            else
            {
                if(pre == p1) //注意當pre==p1時表示要将p2的節點插入p1的頭節點
                {
                    tmp->val = p2->val;
                    tmp->next = pre;
                    pre = tmp;
                    l1 = pre;
                    p2 = p2->next;
                }
                else
                {
                    tmp->val = p2->val;
                    pre->next = tmp;
                    tmp->next = p1;
                    p2 = p2->next;
                    pre = tmp;

                }
            }
        }

        while(p2)
        {
            ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
            tmp->val = p2->val;
            tmp->next = NULL;
            pre->next = tmp;
            pre = tmp;
            p2 = p2->next;
        }

        return l1;
    }