lista vinculada inversa sin temp

Question

¿Hay alguna manera de invertir la lista vinculada sin usar la variable temp en C? Gracias de antemano.

el famoso método:

Element *reverse(Element *head) 
{ 
    Element *previous = NULL; 

    while (head != NULL) { 
     // Keep next node since we trash 
     // the next pointer. 
     Element *next = head->next; 

     // Switch the next pointer 
     // to point backwards. 
     head->next = previous; 

     // Move both pointers forward. 
     previous = head; 
     head = next; 
    } 

    return previous; 
} 

utiliza variable TEMP

Saurabh

Answer 1

en cuenta que su uso es en realidad la generación temp dos swap() llamadas, y puede ser reemplazado con:

swap(head->next,previous); 
swap(previous,head); 

, se puede intercambiar sin temps utilizando XOR, se llama xor swap.

Answer 2

Uso XOR-swaps sobre los punteros a fingir un XOR-linked-list.

implementación se deja al lector como un ejercicio .

Answer 3

enfoque recursivo:

Element *reverse(Element *head, Element **first) 
{ 
    if (head->next == NULL) 
    { 
     *first = head; 
     return head; 
    } 


    Element* NextElement= reverse (head->next, first); 
    NextElement->next = head; 
    head->next = null; 

    return head; 
} 

llamada de función recursiva:

Element *revLinkListHead; 
    reverse(head, &revLinkListHead); 

Answer 4

Si alguien sigue interesado, aquí está la solución que utiliza ninguna variable nueva en absoluto, excepto para aquellos aprobada en recursivo llamada.

public static List invert(List l) { 
    invert(l.next, l, l); 
    l = l.next; 
    breakCycle(l, l); 
    return l; 
} 

private static void invert(List l, List toBeNext, List first) { 
    if(l.next == null) { 
     l.next = toBeNext; 
     first.next = l; 
    } else { 
     invert(l.next, l, first); 
     l.next = toBeNext; 
    } 
} 

private static void breakCycle(List l, List first) { 
    if(l.next == first) { 
     l.next = null; 
    } else { 
     breakCycle(l.next, first); 
    } 
} 

La idea es la siguiente: en primer lugar nos encontramos función invertido de forma recursiva, y aplicarlo de manera que cuando llega al último elemento se le asigna como un elemento al lado de la cabeza (parámetro first). Después de que lo hayamos ejecutado, tendremos una lista invertida pero ciclada, por lo que el head.next actual apuntará a la cabeza de la lista invertida. Reasignamos la cabeza a su siguiente elemento (el jefe real de la lista invertida), y lo último que tenemos que hacer es romper el ciclo. ¡Entonces llamamos al breakCycle, que hace el trabajo recursivamente!