Definição da Estrutura de Dados

class NoLista {
    int valor;
    NoLista proximo;

    NoLista(int x) {
        valor = x;
    }
}

Abordagem 1: Inserção Sequencial Esta solução insere eleementos das listas posteriores nas listas anteriorse de forma sequencial, com complexidade temporal O(K*N).

public static NoLista mesclarKListas(NoLista[] listas) {
    int quantidade = listas.length;
    NoLista[] ponteirosInicio = new NoLista[quantidade];
    
    for(int i = 0; i < quantidade; i++) {
        ponteirosInicio[i] = listas[i];
    }
    
    NoLista cabeca = new NoLista(Integer.MIN_VALUE);
    cabeca.proximo = null;
    NoLista atual = cabeca;
    NoLista anterior = cabeca;
    NoLista temporario = null;
    
    for(int i = 0; i < quantidade; i++) {
        atual = cabeca;
        anterior = cabeca;
        
        while(ponteirosInicio[i] != null && atual != null) {
            if(ponteirosInicio[i].valor > atual.valor) {
                anterior = atual;
                atual = atual.proximo;
            } else {
                temporario = ponteirosInicio[i].proximo;
                ponteirosInicio[i].proximo = atual;
                anterior.proximo = ponteirosInicio[i];
                ponteirosInicio[i] = temporario;
                atual = anterior.proximo;
            }
        }
        
        if(atual == null) {
            anterior.proximo = ponteirosInicio[i];
        }
    }
    
    return cabeca.proximo;
}

Abordagem 2: Mesclagem por Divisão e Conquista Esta abordagem utiliza o paradigma de divisão e conquista, dividindo o problema recursiavmente e mesclando as soluções parciais.

public static NoLista mesclarKListasDivisaoConquista(NoLista[] listas) {
    if(listas == null || listas.length == 0) {
        return null;
    }
    return processarDivisao(listas, 0, listas.length - 1);
}

private static NoLista processarDivisao(NoLista[] listas, int esquerda, int direita) {
    if(esquerda < direita) {
        int meio = (esquerda + direita) / 2;
        NoLista parteEsquerda = processarDivisao(listas, esquerda, meio);
        NoLista parteDireita = processarDivisao(listas, meio + 1, direita);
        return mesclarDuasListas(parteEsquerda, parteDireita);
    }
    return listas[esquerda];
}

public static NoLista mesclarDuasListas(NoLista lista1, NoLista lista2) {
    NoLista ponteiro1 = lista1;
    NoLista ponteiro2 = lista2;
    NoLista resultado = new NoLista(0);
    resultado.proximo = null;
    NoLista ultimo = resultado;
    
    while(ponteiro1 != null && ponteiro2 != null) {
        if(ponteiro1.valor <= ponteiro2.valor) {
            ultimo.proximo = ponteiro1;
            ultimo = ultimo.proximo;
            ponteiro1 = ponteiro1.proximo;
        } else {
            ultimo.proximo = ponteiro2;
            ultimo = ultimo.proximo;
            ponteiro2 = ponteiro2.proximo;
        }
    }
    
    if(ponteiro1 != null) {
        ultimo.proximo = ponteiro1;
    }
    
    if(ponteiro2 != null) {
        ultimo.proximo = ponteiro2;
    }
    
    return resultado.proximo;
}

Exemplo de Teste

public static void main(String[] args) {
    NoLista primeiraLista = new NoLista(1);
    primeiraLista.proximo = new NoLista(4);
    primeiraLista.proximo.proximo = new NoLista(7);
    
    NoLista segundaLista = new NoLista(2);
    segundaLista.proximo = new NoLista(5);
    segundaLista.proximo.proximo = new NoLista(8);
    
    NoLista terceiraLista = new NoLista(3);
    terceiraLista.proximo = new NoLista(6);
    terceiraLista.proximo.proximo = new NoLista(9);
    
    NoLista[] conjuntoListas = {primeiraLista, segundaLista, terceiraLista};
    NoLista resultado = mesclarKListasDivisaoConquista(conjuntoListas);
    
    NoLista percorredor = resultado;
    while(percorredor != null) {
        System.out.println(percorredor.valor);
        percorredor = percorredor.proximo;
    }
}