合并两个有序的链表

public class leetcode23 {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) return null;

        ListNode res = lists[0];

        for (int i = 1; i < len; i++) {
            res = merge2Lists(res, lists[i]);
        }

        return res;
    }

    // 合并两个有序链表 时间复杂度为O（n+m），原地计算所以空间复杂度为O（1）
    public ListNode merge2Lists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // 头结点head，只是起到哨兵的作用；尾节点tail用来链接
        ListNode head = new ListNode(0);
        ListNode tail = head, ptr_1 = l1, ptr_2 = l2;

        while (ptr_1 != null && ptr_2 != null) {
            if (ptr_1.val <= ptr_2.val) {
                tail.next = ptr_1;
                ptr_1 = ptr_1.next;
            } else {
                tail.next = ptr_2;
                ptr_2 = ptr_2.next;
            }
            tail = tail.next;
        }

        // 如果存在某一个链表有剩余
        tail.next = (ptr_1 == null)? ptr_2: ptr_1;
        return head.next;
    }
}