知乎ID: 码蹄疾
码蹄疾，毕业于哈尔滨工业大学。
小米广告第三代广告引擎的设计者、开发者；
负责小米应用商店、日历、开屏广告业务线研发；
主导小米广告引擎多个模块重构；
关注推荐、搜索、广告领域相关知识;

题目

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

示例：

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

分析

有序链表合并，每次都取两个中较小的一个，直到其中一个遍历到链表结尾结束遍历。
如果这时候还是剩下的元素，肯定比之前的元素都大，直接添加到链表结尾就好。

code

/** * 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) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode merged = null; ListNode head = null; while (l1 != null && l2 != null) { if (head == null) { if (l1.val < l2.val) { merged = l1; l1 = l1.next; } else { merged = l2; l2 = l2.next; } head = merged; continue; } if (l1.val < l2.val) { merged.next = l1; l1 = l1.next; } else { merged.next = l2; l2 = l2.next; } merged = merged.next; } while (l1 != null) { merged.next = l1; l1 = l1.next; merged = merged.next; } while (l2 != null) { merged.next = l2; l2 = l2.next; merged = merged.next; } return head; } }