Concatenate two lists simply linked


I am trying to perform a procedure that when I receive two lists I upload it in a third one.

My strategy is simple:

  • As long as there is an element in list1 - > Add item in Concatenated list.
  • As long as there is an element in the list2 - > Add item in Concatenated list.

However, when it comes to linking lists1, with the concatenated list I am not managing to do it correctly.

The underlying node type is the following:

struct NodoListaSE
    int info;
    NodoListaSE* sig;

And my procedure (I set the example for a single list):

void concatenarLista(NodoListaSE* lista1, NodoListaSE* lista2, NodoListaSE *& listaConcatenada)
    NodoListaSE* nuevo = new NodoListaSE();
    while(lista1 != NULL)
        //Asigno el valor de la lista 1 al nuevo nodo.
        nuevo -> info = lista1 -> info;

        nuevo -> sig = listaConcatenada; // <-- Termino agregando elemento de manera infinita.

        listaConcatenada = nuevo;

        lista1 = lista1 -> sig;

        //Contador rudimentario.
        cout << "Valor " <<endl;

I think my confusion is that I can not, clearly, answer this question:

  • How do I link the new node with the list that passed through a parameter?
  • How do I 'move' from one element to another?
  • I've been using this answer as a guide. And it helped me a lot to be able to insert the last place, print, calculate averages and the highest. But I'm not able to concatenate two lists into a third one.

    asked by jqc 12.11.2017 в 18:36

    3 answers


    The nodes are not lists.

    I have seen this confusion several times in StackOverflow in Spanish, and I find it very curious that so many users make that mistake.

    The code you have provided uses variables named lista whose underlying type is NodoListaSE . And that is as wrong as saying that a step is a ladder, sincerely Do you think the same ?:

    C ++ and C are different languages.

    Initially you had labeled the question with both languages; While it is true that many solutions are indistinct language, both languages have a very differentiated idiosyncrasy and style; in particular, C ++ is usually used more as an object-oriented language, so that loose function of concatenarLista , in C ++ style would be part of an object called ListaSE or it would be a binary addition operator ( + ) but rarely a function loose.


    Taking into account the two previous points, I would propose to create a ready object:

    struct ListaSE
        ListaSE() = default;
        ListaSE(ListaSE &&lista);
        ListaSE(const ListaSE &lista);
        void agrega_dato(int dato);
        ListaSE operator +(const ListaSE &lista) const;
        //      ^^^^^^^^^^ <--- Concatenador
        struct Nodo
            int info = 0;
            Nodo* sig = nullptr;
        Nodo *raiz = nullptr;

    The way to concatenate two lists would be copying all the nodes, I highlight the copy because we want a new list result of concatenating the previous two not a new list with the nodes of the originals. One way to do this would be to copy the lista1 into a new list and then insert the data from lista2 :

    ListaSE operator +(const ListaSE &lista) const
        ListaSE resultado(*this); // Copia de la lista actual.
        for (Nodo *nodo = lista.raiz; nodo; nodo = nodo->sig)
        return resultado;

    For my proposal to work you have to implement the copy constructor ( ListaSE(const ListaSE &lista); ) and the movement constructor ( ListaSE(ListaSE &&lista); ):

    ListaSE::ListaSE(const ListaSE &lista)
        for (Nodo *nodo = lista.raiz; nodo; nodo = nodo->sig)
    ListaSE::ListaSE(ListaSE &&lista)
        raiz = lista.raiz;
        lista.raiz = nullptr;

    You can see the code working in Wandbox 三 へ (へ ਊ) へ ハ ッ ハ ッ .

    answered by 13.11.2017 в 09:22

    If after concatenating lists A and B, you do not need to continue using the original lists; only one pointer is required:

    The last node in list A to point to the first node in list B.

    Think graphically:

    A: N1 - > N2 - > N3 - > NULL

    B: Na - > Nb - > Nc - > NULL

    Then the concatenation:

    C (A, B): N1 - > N2 - > N3 - > (Here NULL is changed by the address of Na) Na - > Nb - > Nc - > NULL

    Programmatically it would be:

        NodoListaSE* concatenarLista(NodoListaSE* lista1, NodoListaSE* lista2)
          NodoListaSE* aux = lista1;
          while (aux->sig != NULL){ // navegar por lista1 hasta el ultimo nodo
            aux = aux->sig;
          /** aqui se que aux apunta al último nodo de lista1,
          solo basta hacer que ultimo_nodo->sig apunte al comienzo de la lista2. Como 
          se pasa argumento (lista1 y lista2) por referencia, la acción se evidencia en todo el 
          aux->sig = lista2; // lista2 apunta al primer nodo de la lista2
          return lista1; // lista concatenada queda en lista1 original

    If you have any other questions, comment on this. Greetings,

    answered by 12.11.2017 в 19:50

    The answer depends on the type of list you use and the semantics of the operation you want to implement.

    As Vicente Oyanedel said, it may be a change in the last node of the first list, so that it points to the first node of the second list.

    Lista1 -> n1 -> n2 -> NULL
    Lista2 -> na -> nb -> NULL
    Litsa1 (concatenada) -> n1 -> n2 -> na -> nb -> NULL

    According to this, the semantics is to add the elements of the second list to the first one. The problem is that you have several lists pointing to the same nodes, which is known as aliasing . You should think if it is convenient to allow the aliasing or in your application this would be wrong, and program accordingly.

    For example, a mishandling of the aliasing would occur if you create a destructor that removes the complete list, freeing the memory of its nodes, after having concatenated it to another list.

    // Se crea una lista con los nodos 1, 2, 3
    Nodo * lista1 = new Lista();
    lista1->add(1, 2, 3);
    // Se crea una lista con los nodos 4 y 5
    Nodo * lista2 = new Lista();
    lista2->add(4, 5);
    // Se concatena: ahora las dos listas apuntan a 4 y 5
    // Imprimimos las listas
    lista1->print();        // lista1: 1, 2, 3, 4, 5
    lista2->print();        // lista2: 4, 5
    // Liberamos memoria de los nodos de lista2 (4 y 5)
    delete lista2;
    // Imprimimos la primera lista
    lista1->print();        // error en tiempo de ejecución

    When trying to access memory areas that have already been released, a runtime error would occur.

    Another option, which I prefer, is to create a function that given two lists, create a new one and insert copies of the nodes of the two. Thus the aliasing is not allowed. This would be accompanied by a function addNodo , that adds a node to the desired list, previous copy of the node.

    In any case, the option to use is your decision, but you have to be consistent at the time of scheduling so that there are no problems with null pointers or liberated zones but still inaccessible.

    I also think that it is better to define Nodo as class , and not as struct , since, after all, it is a class with public members by default, encapsulating the behavior of a node and a separate list.

    Well, I have my node like this:

    class Nodo {
        friend class Lista;
            int valor;
            Nodo * sig;
            Nodo(int v);

    And my list like this:

    class Lista {
            Nodo * primero;
            Nodo * ultimo;
            int elementos;
            void addNodo(Nodo * nodo);
            Lista * concatenar(Lista * l);

    As I have said, the addNodo function copies the node and inserts it into the list, in such a way that the aliasing is prevented.

    The concatenarListas function made it static, it receives two lists and returns a new list that contains copies of the nodes of both.

    The concatenation code with copy is:

    Lista * Lista::concatenar(Lista * l) {
        if (l == NULL) throw "Error: lista nula";
        Lista * lista = new Lista();
        Nodo * nodo = this->primero;
        while (nodo != NULL) {
            nodo = nodo->sig;
        nodo = l->primero;
        while (nodo != NULL) {
            nodo = nodo->sig;
        return lista;

    This function is based on the function addNodo , which does not allow the aliasing , and that is like this:

    void Lista::add(Nodo * n) {
        if (n == NULL) throw "Error: nodo nulo";
        Nodo * copia = new Nodo(n->valor);
        if (elementos == 0) {
            primero = copia;
            ultimo = copia;
        else {
            ultimo->sig = copia;
            ultimo = copia;
    answered by 12.11.2017 в 21:41