Intercambiando nodos en una sola lista vinculada

Question

Estoy tratando de hacer una función swapNode que puede tomar dos nodos y cambiarlos. He creado un algoritmo que funciona si están al menos a 2 nodos de distancia, pero parece que no puedo encontrar un algoritmo que funcione si están más cerca el uno del otro.

Esto es lo que he escrito hasta ahora:

void swapNode(call * &head, call * &first, call * &second){ 
    call * firstPrev = NULL; 
    call * secPrev = NULL; 
    call * current = head; 

    //set previous for first 
    while((current->next != first)){ 
     current = current->next; 
    } 

    firstPrev = current; 
    current = head; 

    //set previous for second 
    while((current->next != second)){ 
     current = current->next; 
    } 

    secPrev = current; 
    current = second->next; 

    //set firstPrev-> next to second 
    firstPrev->next = second; 
    //set secPrev->next to first 
    secPrev->next = first; 
    //set second->next = first->next 
    second->next = first->next; 
    //set first->next to current 
    first->next = current; 

    current = head; 
    while(current->next != NULL){ 
     cout << current->number << endl; 
     current = current->next; 
    } 

    cout << current->number << endl; 
} 

EDIT: ahora tengo esto como mi parte de intercambio, pero todavía no parece funcionar correctamente

//swap firstPrev-> next with second->next 
tmp = firstPrev->next; 
second->next = firstPrev->next; 
second->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

Edit2: Este tampoco parece funcionar, obtengo un fallo seg.

//swap previous's->next 
    tmp =firstPrev->next; 
    secPrev->next = firstPrev->next; 
    secPrev->next = tmp; 
    //swap swap first->next with second->next 
    tmp = first->next; 
    second->next = first->next; 
second->next = tmp; 

Answer 1

Digamos que tenemos:

Node1 -> Node2 -> Node3 -> Node4 -> Node5 

Para intercambiar dos nodos, es necesario intercambiar las next valores de los anteriores cada uno de ellos, y también los next valores de los nodos que desea intercambiar .

Así que para cambiar, por ejemplo, el nodo 2 y Nodo3, que tienen eficacia para intercambiar Node1->next con Node2->next y Node2->next con Node3->next. Eso funcionará, incluso si están uno al lado del otro (o incluso si es el mismo nodo). Por ejemplo:

Intercambiar Node1->next y Node2->next

Node1->next = Node3 
Node2->next = Node2 

Intercambiar Node2->next con Node3->next

Node2->next = Node4 
Node3->next = Node2 

Esto resulta:

Node1 -> Node3 -> Node2 -> Node4 -> Node5 

intercambiado!

Como se describe en la sección de comentarios, si se intercambia el Nodo1 con algo, tendrá que establecer un nuevo encabezado para la lista vinculada.

---

En respuesta a la edición de la pregunta:

Su código para el bombeo de casi derecha. Sin embargo, debe cambiar el firstPrev con secPrev. Simplemente sucedió en mi ejemplo que estábamos intercambiando uno de los valores next del nodo dos veces, porque estaban uno al lado del otro. Pero lógicamente, queremos cambiar el next s de los dos anteriores, y luego cambiar el next s de los nodos reales. Prueba esto:

//swap firstPrev-> next with secPrev->next 
tmp = firstPrev->next; 
secPrev->next = firstPrev->next; 
secPrev->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

Si usted está recibiendo un error de segmentación, compruebe la variable TMP - que podría ser un error de asignación o supresión alguna parte. ¿Dónde obtienes la segfault?

Answer 2

En la mayoría de los escenarios de la vida real, el canje de los valores será la mejor solución:

void swapNode(call * &head, call * &first, call * &second) { 
    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
} 

Si eso no está permitido, entonces usted quiere hacer un intercambio de estilo similar en el -> siguiente en lugar de la -> componente de valor. Y luego haga otro swap en los primerosPrev-> next y secondPrev-> next components. Tenga cuidado con el caso especial donde primero o segundo == cabeza.

Answer 3

Si bien no estoy 100% seguro de que la respuesta debe incluir referencias al puntero del nodo (o punteros a punteros) y esto debería manejar un caso cuando uno de los nodos también es el jefe de la lista.

void swapNodes(node *&first, node *&second) 
{ 
    node *t = second->next; 
    second->next = first->next; 
    first->next = t; 
    t = second; 
    second = first; 
    first = t; 
} 

A continuación, se puede llamar así, por ejemplo:

swapNodes(head, secPrev->next); 

o

swapNodes(firstPrev->next, head); 

o

swapNodes(firstPrev->next, secPrev->next) 

y debería funcionar automágicamente.

EDIT:

swapNodes podrían ser aún más legible:

void swapNodes(node *&first, node *&second) 
{ 
    std::swap(first->next, second->next); 
    std::swap(first, second); 
} 

Answer 4

regla de oro: "Siempre separar datos de punteros y no intercambiar punteros, sólo los datos!". Haga swap explícito sin usar memcpy(), así puede evitar problemas de alineación. No causa ninguna penalización de rendimiento en términos de complejidad algorítmica, pero hace que su código sea más legible y seguro.

Answer 5

Si desea conocer todos los métodos de intercambio de dos nodos en las listas enlazadas en simples C sólo a continuación, visite este enlace:

http://sahilalipuria.wordpress.com/2013/01/21/swapping-two-nodes-of-a-singly-linked-lists-set-2/

Answer 6

void swap() 
{ 
struct node *temp=0,*nxt,*ptr; 
ptr=head; 
int count=0; 
while(ptr) 
{ 
    nxt=ptr->link; 
    if(nxt) 
{ 
    if(count==0) 
    head=nxt; 
    count++; 
    ptr->link=nxt->link; 
    nxt->link=ptr; 
    if(temp!=NULL) 
    temp->link=nxt; 
    temp=ptr; 
    if(ptr->link==NULL) 
    break; 
    ptr=nxt->link->link; 
} 

} }

Answer 7

Aquí P1 es el primer nodo que se va a cambiar, p2 es el segundo nodo que se va a cambiar. Y prevnode es el nodo que es previa de p2

 temp=head; 
     while(temp!=NULL){ 
     if(temp->link==p1){ 
      temp->link=p2; 

      prevnode->link=p2->link; 
      p2->link=p1->link; 
      t=p1->link; 
      while(t!=prevnode) 
       t=t->link; 
       cout<<" YES"; 
      cout<<"["<<t->num<<"] "; 
      p1->link=prevnode->link; 
      prevnode->link=p1; 

      temp=p1; 
     }//if_ 

     cout<<" "<<temp->num;    
     temp=temp->link; 
    } 

Answer 8

Usted tendrá que cambiar también el componente next del nodo anterior, de lo contrario la lista enlazada no permanecerá unido. Tenga en cuenta que mi estructura se llama node.

int swapNode(node *&head * &first, node * &second) 
{ 
    //first we will declare the 
    //previous of the swapping nodes 
    node *firstprev=NULL; 
    node*secprev=NULL; 
    node*current=head; 
    //set previous first 
    while(current->next!=first) 
    { 
     current=current->next; 
    } 
    firstprev=current; 
    //seting 2nd previous 
    while(current->next!=second) 
    { 
     current=current->next; 
    } 

    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
    //swaping next of the nodes 
    firstprev->next=second; 
    secprev->next=first; 
    return; 
} 

Answer 9

Gracias a todos por sus respuestas! Me doy cuenta de que esta pregunta se ha formulado hace casi dos años y que se ha aceptado una respuesta hace tiempo, pero las respuestas me han confundido un poco. Por lo tanto, a pesar de que el encuestador probablemente no se preocupe por las nuevas respuestas, me gustaría agregar mi versión, en caso de que otros lectores también estén confundidos y documenten mi propio enfoque. Parte de esto puede haber sido más apropiado como comentarios, pero todavía no tengo la reputación para comentar.

En primer lugar, no importa la frecuencia con la que lo miro, en la pizarra o en el depurador, no puedo evitar terminar con un ciclo en el primer nodo, es decirseñalándose a sí mismo, si no uso un condicional para distinguir entre casos de nodos adyacentes y no, incluso con los pasos abstractos o el código concreto de la respuesta actualmente aceptada por Smashery. He buscado un poco en Internet para encontrar el código en el estilo de la respuesta actualmente aceptada para evitar dicho condicional, pero para mí es sorprendentemente difícil de evitar y mis búsquedas no han encontrado una solución así (a menos que esté equivocado sobre el propuesto posiblemente sea incorrecto). Si hubiera alguna expresión inteligente que arrojara la dirección del primer nodo cuando son adyacentes y la dirección del sucesor del primer nodo cuando no lo están, entonces ese condicional no sería necesario, porque descubrir el nuevo sucesor del segundo nodo es lo que (aparentemente) necesita. ese condicional.

En segundo lugar, tengo la misma pregunta acerca de las asignaciones consecutivas a las mismas variables en la respuesta aceptada que otros comentaristas. Espero no estar siendo extremadamente denso aquí, pero asignar valores diferentes a la misma variable en secuencia, a menos que tal vez en el caso de los efectos secundarios, para mí nunca parezca dejar la variable con otro valor que la última asignación, sin importar qué configuración de nodos considero, y por lo tanto hace que las asignaciones anteriores aparentemente sean redundantes. Si me equivoco al respecto y ese enfoque de hecho resolvería este problema, habría podido eliminar el último condicional en el siguiente código, que estaba tratando de deshacer cuando miré por primera vez en Internet una solución para intercambiando nodos sin una envoltura especial de nodos adyacentes. No estoy muy seguro, pero sonaba como si Smashery dejara intencionalmente esas tareas repetidas fuera del rigor lógico y para ilustrar mejor el procedimiento; sin embargo, puedo haber malentendido.

En tercer lugar, en este y en otros sitios a menudo he visto la afirmación de otras respuestas repetidas de que es mejor intercambiar el contenido de los nodos, en lugar de los punteros. Por supuesto, en el caso de los enteros simples, como en los ejemplos hasta ahora, aparentemente produce un código más corto y más simple. Sin embargo, cuando discutimos listas enlazadas con nodos que contienen números enteros, generalmente es un sustituto de la estructura de datos de respaldo de un contenedor más complejo y genérico. Como tal, no creo que el intercambio de los contenidos de los nodos sea tan fácil, al menos si la implementación de la estructura de datos no puede hacer suposiciones sobre la semántica de copia de los artículos del contenedor. Además, el hecho de poder intercambiar los contenidos de nodos así me implica que la lista vinculada posee los contenidos de esos nodos, ya que de lo contrario el código fuera del método de la lista enlazada podría contener referencias a los objetos en esos nodos, cuyos valores de repente cambia debajo de ellos.

Admito, sin embargo, que esto podría depender de la semántica del contenedor. Para una matriz, se puede esperar que un método de intercambio cambie el valor debajo de las referencias a un cierto índice de esa matriz. Eso significaría que las referencias no están destinadas a referirse a un objeto específico, sino a una posición en un contenedor que se puede indexar. Si consideramos una lista vinculada como un medio para ordenar solo un conjunto de objetos, que tienen su uso fuera de la lista vinculada, un usuario probablemente esperaría que una operación de intercambio intercambiara solamente la posición, no los contenidos.

Imagine, por ejemplo, que la lista vinculada representa objetos de tipo "automóvil". Cada automóvil tiene un propietario y ese propietario hace referencia a su automóvil mediante un puntero. Ahora suponga que la lista vinculada representa el orden en que se programará el servicio de un conjunto de automóviles para su inspección en un concesionario de automóviles. Si intercambiamos el contenido de dos nodos, para intercambiar los espacios de programación para dos automóviles, y lo hicimos intercambiando sus contenidos, entonces el servicio de mantenimiento ocurriría en el nuevo orden correcto, pero la gente también terminaría siendo propietaria de repente. ¡diferentes autos! (No me importaría intercambiar con un Tesla, porque solo conduzco un Corolla.)

Si la lista vinculada era, como en el ejemplo de la matriz, basada en la semántica de indexación, entonces la posición en el nodo podría simplemente representar el orden en que se cargan los automóviles en un barco para su transporte. En este punto, los autos no tienen ningún dueño y realmente solo nos importa en qué ranura están. Entonces, supongo que realmente no hace daño intercambiar autos, es decir, el contenido de los objetos a los que hacen referencia los nodos.

Finalmente al código. Como dije antes, no he podido evitar la envoltura especial para los nodos adyacentes.

En primer lugar, la definición de un método auxiliar:

int find_node(int v, node* root, node** n, node** pn) { 
    int i = 0; 
    for (*n = root; *n != NULL && (*n)->v != v; ++i) { 
     *pn = *n; 
     *n = (*n)->next; 
    } 
    return i; 
} 

Este método encuentra un nodo por su valor. El número entero devuelto es la posición basada en cero (llámalo su índice si quieres) del nodo en la lista vinculada. Encontré la detección de adyacencia a través de la posición, en lugar de las comparaciones con el puntero, más legible. El comienzo de la lista es root. El método establece n para apuntar al nodo que contiene el valor pasado. En pn, el método almacena el predecesor de n.

El siguiente es el intercambio real:

void swap_nodes(node **root, int v1, int v2) { 
    if (v1 == v2) return; 

    node *n1, *n2, *pn1, *pn2; 

    int p1 = find_node(v1, *root, &n1, &pn1); 
    int p2 = find_node(v2, *root, &n2, &pn2); 

    if (p1 > p2) { 
     std::swap(n1, n2); 
     std::swap(pn1, pn2); 
     std::swap(p1, p2); 
    } 

    if (p1 == 0) *root = n2; 
    else pn1->next = n2; 

    node* nn1 = n1->next; 
    n1->next = n2->next; 

    if (p2 - p1 > 1) { 
     n2->next = nn1; 
     pn2->next = n1; 
    } else { 
     n2->next = n1; 
    } 
} 

Lo siento que he cambiado la firma del método de la OP un poco. Me pareció más conveniente pasar los valores de los nodos para intercambiar, a diferencia de los punteros de nodo. Si pasa solo punteros de nodo a los nodos respectivos, tendría que hacer otro recorrido para encontrar los predecesores con esta solución, lo que me resultó un poco incómodo. Si no podemos distinguir nodos por estos valores, p. los valores no son únicos, sin embargo, necesitaremos punteros a los nodos.

Al igual que con la explicación de find_node anterior, primero encontramos las posiciones, los nodos y los predecesores para los valores de nodo pasados ​​a swap_nodes a través de v1 y v2. Los valores para el primer y segundo nodo se intercambian todos si el segundo nodo a intercambiar aparece antes que el primero. No es mucho código para hacerlo, reduce la carcasa especial y hace que sea un poco más fácil de visualizar.

Ahora, nos quedan solo dos condicionales más, ninguno de los cuales parecía trivial para evitar. Si el primer nodo está a la cabeza de la lista enlazada, es decir, en la posición cero, la raíz necesita apuntar al segundo nodo. De lo contrario, el predecesor del primer nodo apuntará al segundo nodo.

Se debe recordar el valor anterior del sucesor del primer nodo, en caso de que los nodos no sean adyacentes. Entonces, el sucesor del primer nodo se establece en el sucesor actual del segundo nodo. Este es el único cambio que se aplica a todos los casos: el nuevo sucesor del primer nodo siendo el antiguo sucesor del segundo nodo es la única certeza y útil para comenzar con el fin de recordar las operaciones del puntero y su secuencia al implementar este intercambio. .

Por último, si las posiciones de los nodos difieren en más de uno, no son adyacentes. Luego, el nuevo sucesor del segundo nodo se convierte en el antiguo sucesor del primer nodo, que se guardará arriba, y el predecesor del segundo nodo ahora apunta al primer nodo. Si son adyacentes, no hay nodos entre los nodos para intercambiar que necesiten actualización, por lo que simplemente vincular el segundo nodo con el primero es todo lo que queda por hacer.