LeetCode热题100（二十七） —— 21.合并两个有序链表

• 你好，我是杨十一，一名热爱健身的程序员
  
• 在Coding的征程中，不绝探索与成长
  
• LeetCode热题100——刷题记载（不定期更新）
  此系列文章用于记载我在学习 LeetCode热题100 过程中的总结和劳绩
  愿与诸君共同探讨，在代码世界里携手共进，攻克困难，提升自我
  

标题描述

1. 将两个升序链表合并为一个新的 升序 链表并返回。
2. 新链表是通过拼接给定的两个链表的所有节点组成的。
4. 示例 1：
5.         输入：l1 = [1,2,4], l2 = [1,3,4]
6.         输出：[1,1,2,3,4,4]

复制代码

1. 示例 2：
2.         输入：l1 = [], l2 = []
3.         输出：[]
4. 示例 3：
5.         输入：l1 = [], l2 = [0]
6.         输出：[0]
7. 提示：
8.         两个链表的节点数目范围是 [0, 50]
9.         -100 <= Node.val <= 100
10.         l1 和 l2 均按 非递减顺序 排列

复制代码

代码实现

• 思路一：迭代
  

1. class Solution {
2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
3.         ListNode head = new ListNode();
4.         ListNode curNode = head;
5.         while (list1 != null && list2 != null) {
6.             if (list1.val <= list2.val) {
7.                 curNode.next = list1;
8.                 list1 = list1.next;
9.             } else {
10.                 curNode.next = list2;
11.                 list2 = list2.next;
12.             }
13.             curNode = curNode.next;
14.         }
15.         if (list1 == null) curNode.next = list2;
16.         if (list2 == null) curNode.next = list1;
17.         return head.next;
18.     }
19. }

复制代码

• 思路二：递归
  

1. class Solution {
2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
3.         if (list1 == null) return list2;
4.         if (list2 == null) return list1;
5.         if (list1.val <= list2.val) {
6.             list1.next = mergeTwoLists(list1.next, list2);
7.             return list1;
8.         } else {
9.             list2.next = mergeTwoLists(list1, list2.next);
10.             return list2;
11.         }
12.     }
13. }

复制代码

• 数据布局
  

1. public class ListNode {
2.         int val;
3.         ListNode next;
4.         ListNode() {}
5.         ListNode(int val) { this.val = val; }
6.         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7. }

复制代码

思路解析

• 输入：两个链表的头节点 ListNode list1, ListNode list2
  
• 输出：合并后的链表头节点 ListNode newHead
  
• 思路：迭代和递归
  
  
  
  • 从两个待选链表中选择值较小的头节点加入新链表
    
  • 当某个链表的节点率先被选择完后，将另一个链表剩余元素全部毗连至新链表尾部
    
  
  
• 相干知识点
  

---

• 你好，我是杨十一，一名热爱健身的程序员
  
• 在Coding的征程中，不绝探索与成长
  
• LeetCode热题100——刷题记载（不定期更新）
  此系列文章用于记载我在学习 LeetCode热题100 过程中的总结和劳绩
  愿与诸君共同探讨，在代码世界里携手共进，攻克困难，提升自我
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。