LeetCode——21.合并两个有序链表（题解）

布满荆棘的人生 2023-01-01 11:56 109阅读 0赞

[21. 合并两个有序链表][21.]

# 题目描述 #

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

示例：

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

--------------------

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

--------------------

# 最初想法 #

最简单的合并，用头节点和一个index节点去创建合并后的链表。  
每次需要创建一个新的节点空间temp来存放这些节点 **（可优化）**  
最后对还未处理完的节点进行依次遍历。**（可优化）**

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            ListNode head = new ListNode(0,null);
            ListNode index = head;
            ListNode i = l1;
            ListNode j = l2;
            while(i != null && j != null){
        
                ListNode temp = new ListNode(0, null);
                if(i.val < j.val){
        
                    temp.val = i.val;
                    index.next = temp;
                    i = i.next;
                }else{
        
                    temp.val = j.val;
                    index.next = temp;
                    j = j.next;
                }
                index = index.next;
            }
    
            while(i != null){
        
                ListNode temp = new ListNode(i.val, null);
                index.next = temp;
                i = i.next;
                index = index.next;
            }
    
            while(j != null){
        
                ListNode temp = new ListNode(j.val, null);
                index.next = temp;
                j = j.next;
                index = index.next;
            }
    
            return head.next;
        }
    }

## 效率 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

# 进阶想法 #

## 优化合并过程 ##

对于合并过程，`在最初想法的代码中，每次都需要分配新的空间去创建新节点temp`，但是我们可以直接利用原来的节点的空间，直接将index去指向这个节点空间即可。  
并且`不需要用i,j`去遍历链表，`直接用l1,l2`即可

## 优化后续处理 ##

在后续处理中，`最初想法为将所有节点遍历一遍，让index的next依次指向每一个节点`，优化后`其实只需要将未遍历完的链表的头，被index的next指向`即可

## 效率 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]时间复杂度为O(n + m)，空间复杂度为O(1)

# 递归写法 #

[超详细图解递归执行过程 21.合并两个有序链表][21. 1]

[21.]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/4ae6afbcc21d497fab3bbceb83361039.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: /images/20221120/225e56a54a0b4de089f0e04ef2fa0301.png
[21. 1]: https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/chao-xiang-xi-tu-jie-di-gui-zhi-xing-guo-cheng-21h/