Programa Java para invertir una lista enlazada – Part 1

Dado un puntero al Node principal de una lista enlazada, la tarea es invertir la lista enlazada. Necesitamos invertir la lista cambiando los enlaces entre los Nodes. Ejemplos:

Entrada: Encabezado de la siguiente lista enlazada  
       1->2->3->4->NULL
Salida: La lista enlazada debe cambiarse a
       4->3->2->1->NULL

Entrada: Encabezado de la siguiente lista enlazada  
       1->2->3->4->5->NULL
Salida: La lista enlazada debe cambiarse a
       5->4->3->2->1->NULL

Entrada: NULL
Salida: NULL

Entrada: 1->NULO
Salida: 1->NULO

Método iterativo:

// Java program for reversing the linked list
 
class LinkedList {
 
    static Node head;
 
    static class Node {
 
        int data;
        Node next;
 
        Node(int d) {
            data = d;
            next = null;
        }
    }
 
    /* Function to reverse the linked list */
    Node reverse(Node node) {
        Node prev = null;
        Node current = node;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        node = prev;
        return node;
    }
 
    // prints content of double linked list
    void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
 
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(85);
        list.head.next = new Node(15);
        list.head.next.next = new Node(4);
        list.head.next.next.next = new Node(20);
         
        System.out.println("Given Linked list");
        list.printList(head);
        head = list.reverse(head);
        System.out.println("");
        System.out.println("Reversed linked list ");
        list.printList(head);
    }
}
 
 
// This code has been contributed by Mayank Jaiswal

Given Linked list
85 15 4 20 
Reversed linked list 
20 4 15 85 

Complejidad de tiempo: O(N), donde N es la longitud de la lista enlazada dada
Espacio auxiliar: O(1)

Un método recursivo más simple y de cola:

// Java program for reversing the Linked list
 
class LinkedList {
 
    static Node head;
 
    static class Node {
 
        int data;
        Node next;
 
        Node(int d) {
            data = d;
            next = null;
        }
    }
 
    // A simple and tail recursive function to reverse
    // a linked list. prev is passed as NULL initially.
    Node reverseUtil(Node curr, Node prev) {
 
        /* If last node mark it head*/
        if (curr.next == null) {
            head = curr;
 
            /* Update next to prev node */
            curr.next = prev;
            return null;
        }
 
        /* Save curr->next node for recursive call */
        Node next1 = curr.next;
 
        /* and update next ..*/
        curr.next = prev;
 
        reverseUtil(next1, curr);
        return head;
    }
 
    // prints content of double linked list
    void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
 
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(5);
        list.head.next.next.next.next.next = new Node(6);
        list.head.next.next.next.next.next.next = new Node(7);
        list.head.next.next.next.next.next.next.next = new Node(8);
 
        System.out.println("Original Linked list ");
        list.printList(head);
        Node res = list.reverseUtil(head, null);
        System.out.println("");
        System.out.println("");
        System.out.println("Reversed linked list ");
        list.printList(res);
    }
}
// This code has been contributed by Mayank Jaiswal

Original Linked list 
1 2 3 4 5 6 7 8 

Reversed linked list 
8 7 6 5 4 3 2 1 

Complejidad de tiempo: O(N), donde N es la longitud de la lista enlazada dada
Espacio auxiliar: O(1)

Consulte el artículo completo sobre Invertir una lista vinculada para obtener más detalles.