【Hot100】23. 合并K个升序链表

23. 合并K个升序链表
困难题
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路：逐一合并两条链表

首先复习一下【Hot100】21. 合并两个有序链表

下面分别贴出「merge2Lists」的「递归」 和 「迭代」两种实现 ：

• 递归

class Solution {
    
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        if (list1 == null) {
    
            return list2;
        }
        else if (list2 == null) {
    
            return list1;
        }
        else if (list1.val < list2.val) {
    
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else {
    
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }
}

• 迭代

private ListNode merge2Lists(ListNode l1, ListNode l2) {
    
    ListNode dummyHead = new ListNode(0);
    ListNode tail = dummyHead;
    while (l1 != null && l2 != null) {
    
        if (l1.val < l2.val) {
    
            tail.next = l1;
            l1 = l1.next;
        } else {
    
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }

    tail.next = l1 == null? l2: l1;

    return dummyHead.next;
}

• 逐一合并

class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        ListNode res = null;
        for (ListNode list: lists) {
    
            res = merge2Lists(res, list);
        }
        return res;
    }
}

两两合并对 1 进行优化：

• 两两合并 - 迭代

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        if (lists.length == 0) {
    
            return null;
        }
        int k = lists.length;
        while (k > 1) {
    
            int idx = 0;
            for (int i = 0; i < k; i += 2) {
    
                if (i == k - 1) {
    
                    lists[idx++] = lists[i];
                } else {
    
                    lists[idx++] = merge2Lists(lists[i], lists[i + 1]);
                }
            }
            k = idx;
        }
        return lists[0];
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
    
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (l1 != null && l2 != null) {
    
            if (l1.val < l2.val) {
    
                tail.next = l1;
                l1 = l1.next;
            } else {
    
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        tail.next = l1 == null? l2: l1;

        return dummyHead.next;
    }
}

• 两两合并 - 递归

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        if (lists.length == 0) {
    
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int lo, int hi) {
    
        if (lo == hi) {
    
            return lists[lo];
        }
        int mid = lo + (hi - lo) / 2;
        ListNode l1 = merge(lists, lo, mid);
        ListNode l2 = merge(lists, mid + 1, hi);
        return mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        if (list1 == null) {
    
            return list2;
        }
        else if (list2 == null) {
    
            return list1;
        }
        else if (list1.val < list2.val) {
    
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else {
    
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }
}

class Solution {
    
   public ListNode mergeKLists(ListNode[] lists) {
    
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    //合并函数
    private ListNode merge(ListNode[] lists, int left, int right) {
    
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    //合并两个升序链表
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
    	ListNode dummyHead = new ListNode(0);
    	ListNode cur = dummyHead;
    	while (l1 != null && l2 != null) {
    
        	if (l1.val < l2.val) {
    
            	cur.next = l1;
            	l1 = l1.next;
        	} else {
    
                cur.next = l2;
            	l2 = l2.next;
        	}
            //移动合并链表的下一个节点
        	cur = cur.next;
    	}
        
        //如果链表1为空了，则合并链表把链表2剩下的接在后面，否则接链表1节点
        if(l1 == null){
    
        	cur.next = l2;
        }else{
    
        	cur.next = l1;
        }
    	//cur.next = l1 == null? l2 : l1;
    	return dummyHead.next;
	}
}