题解 | #合并k个已排序的链表#

/*class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
 */
export function mergeKLists(lists: ListNode[]): ListNode {
    // write code here
  let start = 0
  let end = lists.length - 1
  /**
  * 用类似归并排序的方式，拆分lists数组，以实现两两链表的合并
  */
  const recur = (start, end) => {
    if (start > end) {
      return null
    }
    if (start === end) {
      return lists[start]
    }
    const mid = Math.floor((start + end) / 2)
    let left = recur(start, mid)
    let right = recur(mid + 1, end)
	// 为了方便调整指针，用一个空的前置节点
    let lp: ListNode = new ListNode(-1, null)
    lp.next = left
    let rp: ListNode = new ListNode(-1, null)
    rp.next = right
    let head: ListNode = null
    let tail: ListNode

    // 处理只有lp.next为空，或者rp.next为空的情况
    if (!lp.next) {
      head = rp.next
      return head
    } else if (!rp.next) {
      head = lp.next
      return head
    }
    
    while (lp.next && rp.next) {
      let smaller
      let leftSmaller
      if (lp.next.val <= rp.next.val) {
        smaller = lp.next
        leftSmaller = true
      } else {
        smaller = rp.next
        leftSmaller = false
      }

      if (!head) {
        head = smaller
      } else {
        tail.next = smaller
      }
      tail = smaller
      if (leftSmaller) {
        lp.next = lp.next.next
      } else {
        rp.next = rp.next.next
      }      
    }
	// lp.next 或者 rp.next还有剩余节点则直接连进tail.next
    if (lp.next) {
      tail.next = lp.next
    } else if (rp.next) {
      tail.next = rp.next
    }
    return head
  }

  return recur(start, end)
}