Leetcode 合并两个有序链表

问题描述

先上代码：

/**
 * 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 head = null;
        if (l1.val <= l2.val) {
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);  
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

解析：

这其实就是在考察归并排序，先判断两个链表的表头，取出较小者作为新链表的元素，对应的链表指针后移，然后不断重复这个过程直到有一个链表被取空。取空之后再判断一下被取空的是哪一个链表，把剩下那一串补上就行。本题巧妙的地方在于可以写成递归形式，简洁而优雅。

时间复杂度：

O( m + n)，与两个链表的长度之和成正比