LeetCode刷题实战21：合并两个有序链表 / 开普饭

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做合并两个有序链表，我们先来看题面：

https://leetcode-cn.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

题意

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

样例

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

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

题解

两个有序链表的排序，实际上可以看成一个单链表使用归并排序的最后一个环节：“将两个排好序的子序列合并为一个子序列：每次都是从未比较的两个子序列的最小值中选出一个更小值”。

/**
* 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 temp=new ListNode(0);
        ListNode head=temp;//保留头节点的引用
        while(l1!=null&&l2!=null){
           if(l1.val<l2.val)
           {
               temp.next=l1;
               l1=l1.next;
           }
           else
           {
               temp.next=l2;
               l2=l2.next;
           }
           temp=temp.next;
        }
        if(l1==null) temp.next=l2;//l1子序列为空，则直接拼届l2
        if(l2==null) temp.next=l1;
        return head.next;//返回头节点指向的序列
    }
}