Merge Two Sorted Lists——解题报告

喜欢ヅ旅行 2022-08-08 06:21 3阅读 0赞

【题目】

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.

【分析】

不要忘记先判断两个链表是否有空链表。其余的使用递归和非递归方式，都可以实现。

【代码】

递归方式：

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

非递归方式：

class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode* mergedList = NULL; 
            
            if(l1 == NULL)
                return l2;
            if(l2 == NULL)
                return l1;
            
            if(l1->val < l2->val)
            {
                mergedList = l1;
                mergedList->next = NULL;
                l1 = l1->next;
            }
            else
            {
                mergedList = l2; 
                mergedList->next = NULL;
                l2 = l2->next;
            }
            
            ListNode* p = mergedList;
            while(l1 != NULL && l2 != NULL)
            {
                if(l1->val < l2->val)
                {
                    p->next = l1;
                    l1 = l1->next;
                    p = p->next;
                    p->next = NULL;
                }
                else
                {
                    p->next = l2; 
                    l2 = l2->next;
                    p = p->next;
                    p->next = NULL;
                }
            }
            
            if(l1 != NULL)
                p->next = l1; 
            else if(l2 != NULL)
                p->next = l2;
            
            return mergedList;
            
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made b

旧城等待，/ 2022年08月21日 04:08/ 0 赞/ 2 阅读

相关 LeetCode--Merge Two Sorted Lists

Problem: > Merge two sorted linked lists and return it as a new list. The new > list

àì夳堔傛蜴生んèń/ 2022年08月17日 14:27/ 0 赞/ 5 阅读

相关 Merge Two Sorted Lists——解题报告

【题目】 Merge two sorted linked lists and return it as a new list. The new list sho

喜欢ヅ旅行/ 2022年08月08日 06:21/ 0 赞/ 4 阅读

相关 LeetCode-Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made b

小咪咪/ 2022年08月06日 15:16/ 0 赞/ 13 阅读

相关 java: Merge-two-sorted-lists

【问题描述】: > Merge two sorted linked lists and return it as a new list. The new list shoul

太过爱你忘了你带给我的痛/ 2022年06月17日 09:42/ 0 赞/ 161 阅读

相关 leetcode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made b

妖狐艹你老母/ 2022年06月09日 08:00/ 0 赞/ 188 阅读

相关 Merge Two Sorted Lists

Leetcode 21. Merge Two Sorted Lists Merge two sorted linked lists and return it as a ne

喜欢ヅ旅行/ 2022年06月09日 04:35/ 0 赞/ 109 阅读

相关【leetcode】21. Merge Two Sorted Lists

> Merge two sorted linked lists and return it as a new list. The new list should be made

悠悠/ 2022年01月21日 10:27/ 0 赞/ 189 阅读

相关 [leetcode-21-Merge Two Sorted Lists]

Merge two sorted linked lists and return it as a new list. The new list should be made

╰+哭是因爲堅強的太久メ/ 2022年01月06日 11:17/ 0 赞/ 151 阅读

相关 Merge Two Sorted Lists

题目描述： Merge two sorted linked lists and return it as a new list. The new list should be

本是古典何须时尚/ 2022年01月05日 10:39/ 0 赞/ 162 阅读