题解|#23. 合并K个升序链表#

• 使用循环两两合并
• 边界条件
  • 输入为空，直接返回
  • 输入只有一个，直接返回第1个
  • 循环合并第1，2，再同第3、4……n

核心逻辑

• 创建一个新节点为头部
• 返回时，返回此节点的next
• 需要一个temp变量，在新链表中移动
• 待合并两个链表，使用后，分别指向next

package pers.sloera.leetcode.mergeKLists;

import pers.sloera.common.ListNode;

/**
 * class pers.sloera.leetcode.mergeKLists
 * user sloera
 * date 2022/3/2
 */
public class Solution {
  public static void main(String[] args) {
    final Solution solution = new Solution();
    ListNode[] lists = new ListNode[]{};
    final ListNode listNode = solution.mergeKLists(lists);
    System.out.println(listNode);
  }

  public ListNode mergeKLists(ListNode[] lists) {
    //         采用递归的思想
    if (lists.length == 0) {
      return null;
    }
    if (lists.length == 1) {
      return lists[0];
    }
    ListNode res = mergeTwoLists(lists[0], lists[1]);
    // ListNode temp = res;
    for (int i = 2; i < lists.length; i++) {
      // temp.next = mergeTwolists(mergeTwolists(),lists[])
      res = mergeTwoLists(res, lists[i]);
    }
    return res;
  }

  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode temp = new ListNode(0);    //哑节点
    ListNode res = temp;    //保存头节点。
    if (l1 == null) {  //	某个链表为空，返回另一个
      return l2;
    } else if (l2 == null) {
      return l1;
    } else {
      //        	temp.next = l1;
      while (true) {
        if (l1.val < l2.val) {
          temp.next = l1;
          temp = temp.next;
          l1 = l1.next;
        } else {
          temp.next = l2;
          temp = temp.next;
          l2 = l2.next;
        }
        if (l1 == null) {
          temp.next = l2;
          return res.next;
        } else if (l2 == null) {
          temp.next = l1;
          return res.next;
        }
      }
    }

  }
}