精选50题之 21. 合并两个有序链表

你的名字 2024-04-18 10:06 50阅读 0赞

### 腾讯精选练习（50 题）之 21. 合并两个有序链表 ###

*   *  原题目链接
     *  题目分析
     *  解题思路
     *  代码实现
     *  另一种思路

## [原题目链接][Link 1] ##

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

> 示例：  
> 输入：1->2->4, 1->3->4  
> 输出：1->1->2->3->4->4

## 题目分析 ##

链表合并，可以认为是元素之间重新连线，可以使用递归的思路。

## 解题思路 ##

首先判断是否有空链表存在，然后递归求解
    ①list1[0]+merge(list1[1:], list2)		当list1[0]<list2[0]时
    ②list2[0]+merge(list1, list2[1:])		当list1[0]>=list2[0]

## 代码实现 ##

/**
     * 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) {
        
            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;
            }
        }
    };

运行结果  
![在这里插入图片描述][20190905083355189.png]  
复杂度分析

*  时间复杂度：O(n+m)
 *  空间复杂度：O(n+m)

## 另一种思路 ##

由于链表有序，当一个链表已经完成比较后，可以将另一个链表的剩余部分直接接在其后，无需继续比较。但这与“递归”解法中的

代码实现

/**
     * 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) {
        
            if(!l1) return l2;
            if(!l2) return l1;
            ListNode* head = new ListNode(0);
            ListNode* cur = head;
            while(l1 && l2)
            {
        
                if(l1 -> val <= l2 -> val)
                {
        
                    cur -> next = l1;
                    l1 = l1 -> next;
                }
                else
                {
        
                    cur -> next = l2;
                    l2 = l2 -> next;
                }
                cur = cur -> next;
            }
            cur -> next = l1 == NULL ? l2 : l1;
            return head->next;
        }
    };

运行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
复杂度分析

*  时间复杂度：O(n+m)
 *  空间复杂度：O(1)

[Link 1]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[20190905083355189.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/9a11d4f3efba468a87ea42da54549648.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/fff0a87b837f4c3b9b69b9bf062b3f18.png