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

package org.example.test;

import lombok.Getter;
import lombok.Setter;

import java.util.ArrayList;

public class MergeKListsTest {

    @Setter
    @Getter
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0) {
            return null;
        }
        ListNode node = lists.get(0);
        for (int i = 1; i < lists.size(); i++) {
            node = merge(node, lists.get(i));
        }
        return node;
    }

    // 归并链表排序，用一个临时头结点辅助。每次归并返回一个链表，然后和下个链表归并排序
    private ListNode merge(ListNode node, ListNode listNode) {
        ListNode ret = new ListNode(0);
        ListNode cur = ret;
        ListNode cur1 = node;
        ListNode cur2 = listNode;
        for (; cur1 != null && cur2 != null; ) {
            int val1 = cur1.val;
            int val2 = cur2.val;
            if (val1 >= val2) {
                ret.next = cur2;
                ret = cur2;
                cur2 = cur2.next;
            } else {
                ret.next = cur1;
                ret = cur1;
                cur1 = cur1.next;
            }
        }
        while (cur1 != null) {
            ret.next = cur1;
            ret = cur1;
            cur1 = cur1.next;

        }
        while (cur2 != null) {
            ret.next = cur2;
            ret = cur2;
            cur2 = cur2.next;

        }
        return cur.next;
    }
}