“Selección Ordena Lista vinculada Java” Código de respuesta

Selección Ordena Lista vinculada Java

// Java implementation of the approach
class GFG {
 
    // Linked List Node
    static class Node {
        int data;
        Node next;
    };
 
    // Utility function to create a
    // new Linked List Node
    static Node newNode(int val)
    {
        Node temp = new Node();
 
        temp.data = val;
 
        temp.next = null;
 
        return temp;
    }
 
    // Function to sort a linked list using selection
    // sort algorithm by swapping the next pointers
    static Node selectionSort(Node head)
    {
        Node a, b, c, d, r;
 
        a = b = head;
 
        // While b is not the last node
        while (b.next != null) {
 
            c = d = b.next;
 
            // While d is pointing to a valid node
            while (d != null) {
 
                if (b.data > d.data) {
 
                    // If d appears immediately after b
                    if (b.next == d) {
 
                        // Case 1: b is the head of the linked list
                        if (b == head) {
 
                            // Move d before b
                            b.next = d.next;
                            d.next = b;
 
                            // Swap b and d pointers
                            r = b;
                            b = d;
                            d = r;
 
                            c = d;
 
                            // Update the head
                            head = b;
 
                            // Skip to the next element
                            // as it is already in order
                            d = d.next;
                        }
 
                        // Case 2: b is not the head of the linked list
                        else {
 
                            // Move d before b
                            b.next = d.next;
                            d.next = b;
                            a.next = d;
 
                            // Swap b and d pointers
                            r = b;
                            b = d;
                            d = r;
 
                            c = d;
 
                            // Skip to the next element
                            // as it is already in order
                            d = d.next;
                        }
                    }
 
                    // If b and d have some non-zero
                    // number of nodes in between them
                    else {
 
                        // Case 3: b is the head of the linked list
                        if (b == head) {
 
                            // Swap b.next and d.next
                            r = b.next;
                            b.next = d.next;
                            d.next = r;
                            c.next = b;
 
                            // Swap b and d pointers
                            r = b;
                            b = d;
                            d = r;
 
                            c = d;
 
                            // Skip to the next element
                            // as it is already in order
                            d = d.next;
 
                            // Update the head
                            head = b;
                        }
 
                        // Case 4: b is not the head of the linked list
                        else {
 
                            // Swap b.next and d.next
                            r = b.next;
                            b.next = d.next;
                            d.next = r;
                            c.next = b;
                            a.next = d;
 
                            // Swap b and d pointers
                            r = b;
                            b = d;
                            d = r;
 
                            c = d;
 
                            // Skip to the next element
                            // as it is already in order
                            d = d.next;
                        }
                    }
                }
                else {
 
                    // Update c and skip to the next element
                    // as it is already in order
                    c = d;
                    d = d.next;
                }
            }
 
            a = b;
            b = b.next;
        }
 
        return head;
    }
 
    // Function to print the list
    static void printList(Node head)
    {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
 
    // Driver Code
    public static void main(String args[])
    {
        Node head = newNode(5);
        head.next = newNode(4);
        head.next.next = newNode(3);
 
        head = selectionSort(head);
 
        printList(head);
    }
}
 
// This code is contributed by Arnab Kundu