How to concatenate two linked lists?

Question

How to concatenate two linked lists?

Navigation

#1 by (1 votes)
#2 by (-2 votes)

1

I created this code by initializing a list, however I need to improve it, creating a function that concatenates two and at the end print the value of the two concatenated ones ... That, I do not know how to do it.

Suggested Prototype: no *concatena(no * inicio1, no * inicio2);

Parameters: Pointer to the beginning of the 1st. list (which can be NULL) and pointer to the beginning of the 2nd. list (which can be NULL).

Return: Pointer to the beginning of the resulting list of concatenation

 //Lista encadeada Simples
//Imprimindo a lista

#include <iostream>
using namespace std;

struct No {
    //Variavel Valor
    int valor;
    //Ponteiro para o próximo Nó
    No * ptr;
};
No * inserirInicio(No * lista, int num);

void imprimir(No * lista);
main(){
    //Declara e inicializa a LIsta
    //O Ponteiro chamado de LISTA e é NULO/Vazio
    No * lista = NULL;
    //Recebera as alterações feitas com a função abaixo

    lista = inserirInicio(lista, 10);
    lista = inserirInicio(lista, 20);
    lista = inserirInicio(lista, 30);
    lista = inserirInicio(lista, 40);
    lista = inserirInicio(lista, 50);
    imprimir(lista);


}

No * inserirInicio(No * lista, int num)
{
        //Variavel temporária
        No * tmp;
        //Se esta vazia Eu crio o elemento e aponto a lista para Ele
        //Aponta para o nov nó
        tmp = new No;
        //Configurando o novo valor
        //Guardo na variavel NUM
        tmp -> valor = num;
        //Apontar para o primeiro cara
        tmp -> ptr = lista;
        lista = tmp;
        //Retorna o novo inicio da lista
        return lista;
    }

//Imprimindo os valores
void imprimir(No * lista)
{
    No * atual;
    atual = lista;//atual aponta para lista
    while(atual!= NULL)
    {
        cout << atual -> valor << endl;
        atual = atual -> ptr;
    }
}

c++

asked by anonymous 21.11.2014 / 15:52

2 answers

-2

Lista* concatList(Lista* a, Lista* b){

    Lista* temp = b;
    while(temp != NULL){
        a = inserirFim(a, temp->item);
        temp = temp->prox;
    }
    return a;
}

15.09.2018 / 07:34

Footer Alignment [closed] Popular table with HTML table data

score 1 · Accepted Answer

Concatenation between two lists has a very simple and very interesting solution, which is a property of the list type itself:

To do this, you must first take these properties into account: each No stores only one pointer to the next list item, not the previous list item. This means, therefore, that the last No of a list does not point to No some (and, in the case of your program, the last No itself is null). Secondly, concatenating, by definition, is the union of two sets by their ends. In this case, the end of inicio1 and the start of inicio2 in the No *concatena(No * inicio1, No * inicio2); function.

So, to do the concatenation, you should look for the last No of inicio1 and inserí-lo ao início of inicio2 .

For example:

No *concatena(No * inicio1, No * inicio2){
    No* fim = NULL;
    No* iterador = inicio1;
    while(iterador->ptr != NULL){
        iterador = iterador->ptr;
    }
    iterador = inserirInicio(inicio2, iterador->valor);
}