【LeetCode】 21. 合并两个有序链表

￡神魔★判官ぃ 2021-06-10 20:37 428阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

1.  总的思路吧，两个ListNode比较值的大小，然后要小的那个，剩下的依次向后遍历
2.  一直到一个ListNode为空，就直接追加两外一个链表全部的内容
3.  这样来做，时间复杂度和空间复杂度都是 m+n

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            ListNode res = new ListNode(-1);
            ListNode temp = res;
            while (l1 != null && l2 != null) { 
                ListNode node;
                if (l1.val > l2.val) { 
                    node = new ListNode(l2.val);
                    l2 = l2.next;
                } else { 
                    node = new ListNode(l1.val);
                    l1 = l1.next;
                }
                temp.next = node;
                temp = temp.next;
            }
            // 追加剩余的那个链表
            ListNode listNode = l1 == null ? l2 : l1;
            while (listNode != null) { 
                temp.next = new ListNode(listNode.val);
                temp = temp.next;
                listNode = listNode.next;
            }
            return res.next;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/7edac8d0d6a8410895b16adf63b194f9.png