¿Cómo intercambiar dos elementos en una lista enlazada en Java?

Dada una Lista Enlazada , la tarea es intercambiar dos elementos sin alterar sus enlaces. Hay varias formas de intercambiar. Los elementos se pueden intercambiar intercambiando los elementos dentro de los Nodes y intercambiando los Nodes completos. 

Ejemplo:

Input :- 10->11->12->13->14->15
         element1 = 11
         element2 = 14
         
Output :- 10->14->12->13->11->15

Método 1: usar el método de conjunto incorporado

Intercambie los dos elementos en una lista enlazada utilizando el método Java.util.LinkedList.set() . Para lograr el resultado deseado, primero, asegúrese de que ambos elementos proporcionados estén disponibles en la Lista vinculada. Si alguno de los elementos está ausente, simplemente regrese. Utilice el método set() para establecer la posición del elemento 1 en la del elemento 2 y viceversa.

A continuación se muestra el código para el enfoque anterior:

// Swapping two elements in a Linked List in Java
  
import java.util.*;
  
class GFG {
    public static void main(String[] args)
    {
  
        LinkedList<Integer> ll = new LinkedList<>();
  
        // Adding elements to Linked List
        ll.add(10);
        ll.add(11);
        ll.add(12);
        ll.add(13);
        ll.add(14);
        ll.add(15);
  
        // Elements to swap
        int element1 = 11;
        int element2 = 14;
  
        System.out.println("Linked List Before Swapping :-");
  
        for (int i : ll) {
            System.out.print(i + " ");
        }
  
        // Swapping the elements
        swap(ll, element1, element2);
        System.out.println();
        System.out.println();
  
        System.out.println("Linked List After Swapping :-");
  
        for (int i : ll) {
            System.out.print(i + " ");
        }
    }
  
    // Swap Function
    public static void swap(LinkedList<Integer> list,
                            int ele1, int ele2)
    {
  
        // Getting the positions of the elements
        int index1 = list.indexOf(ele1);
        int index2 = list.indexOf(ele2);
  
        // Returning if the element is not present in the
        // LinkedList
        if (index1 == -1 || index2 == -1) {
            return;
        }
  
        // Swapping the elements
        list.set(index1, ele2);
        list.set(index2, ele1);
    }
}

Linked List Before Swapping :-
10 11 12 13 14 15 

Linked List After Swapping :-
10 14 12 13 11 15

Complejidad de tiempo: O(N), donde N es la longitud de la lista enlazada

Método 2: Usando nuestra propia Lista Vinculada

A continuación se muestra la implementación del enfoque anterior:

// Java Program to Swap Two Elements in a LinkedList
class Node {
    int data;
    Node next;
    Node(int d)
    {
        data = d;
        next = null;
    }
}
  
class LinkedList {
    Node head; // head of list
  
    // Function to swap Nodes x and y in
    // linked list by changing links
    public void swapNodes(int x, int y)
    {
        // Nothing to do if x and y are same
        if (x == y)
            return;
  
        // Search for x (keep track of prevX and CurrX)
        Node prevX = null, currX = head;
        while (currX != null && currX.data != x) {
            prevX = currX;
            currX = currX.next;
        }
  
        // Search for y (keep track of prevY and currY)
        Node prevY = null, currY = head;
        while (currY != null && currY.data != y) {
            prevY = currY;
            currY = currY.next;
        }
  
        // If either x or y is not present, nothing to do
        if (currX == null || currY == null)
            return;
  
        // If x is not head of linked list
        if (prevX != null)
            prevX.next = currY;
        else // make y the new head
            head = currY;
  
        // If y is not head of linked list
        if (prevY != null)
            prevY.next = currX;
        else // make x the new head
            head = currX;
  
        // Swap next pointers
        Node temp = currX.next;
        currX.next = currY.next;
        currY.next = temp;
    }
  
    // Function to add Node at beginning of list.
    public void push(int new_data)
    {
        // 1. alloc the Node and put the data
        Node new_Node = new Node(new_data);
  
        // 2. Make next of new Node as head
        new_Node.next = head;
  
        // 3. Move the head to point to new Node
        head = new_Node;
    }
  
    // This function prints contents of linked
    // list starting from the given Node
    public void printList()
    {
        Node tNode = head;
        while (tNode != null) {
            System.out.print(tNode.data + " ");
            tNode = tNode.next;
        }
        System.out.println();
    }
  
    // Driver program to test above function
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
  
        // The constructed linked list is:
        // 1->2->3->4->5->6->7
        llist.push(7);
        llist.push(6);
        llist.push(5);
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);
  
        System.out.println("Linked List Before Swapping :-");
        llist.printList();
  
        llist.swapNodes(4, 3);
  
        System.out.println("Linked List After Swapping :-");
        llist.printList();
    }
}

Linked List Before Swapping :-
1 2 3 4 5 6 7 
Linked List After Swapping :-
1 2 4 3 5 6 7

Complejidad de tiempo: O(N), donde N es la longitud de la lista enlazada