Как написать метод перемешивания своего LinkedList^a на Java

Question

Как написать метод перемешивания своего LinkedList^a на Java

Рейтинг: -2Ответов: 1Опубликовано: 26.04.2023

В методе я перемешиваю лист, присваивая узлы исходного списка в случайном порядке временному листу. Я бы хотел отдельно добавлять элементы в начало, конец и середину списка. Я не понимаю, как реализовать добавление в хвост списка, чтобы позже список получался целым, а не разделённым, где одни элементы можно получить только, идя с начала, а другие с конца.

 public void shuffle() {
    MyLinkedListNote<T> headTmp = null;
    MyLinkedListNote<T> tailTmp = null;
    MyLinkedListNote<T> curr = head;

    Random random = new Random();
    int resLength = 0;

    while (curr != null) {
        MyLinkedListNote<T> tmp = curr.next;
        int randomIn = random.nextInt(resLength + 1);

        if (randomIn == 0) {
            curr.next = headTmp;
            headTmp = curr;
            resLength++;
        } else if (randomIn == resLength) {
            curr.next = tailTmp;
            tailTmp = curr;
            resLength++;
        } else {
            MyLinkedListNote<T> currTmp = headTmp;
            int resListIterator = 0;
            while (resListIterator < randomIn - 1) {
                resListIterator++;
                currTmp = currTmp.next;
            }
            curr.next = currTmp.next;
            currTmp.next = curr;
            resLength++;
        }
        curr = tmp;
    }
    head = headTmp;
    tail = tailTmp;
}

java односвязный-список linked-list shuffle

Источник: Stack Overflow на русском

Answer 1

▲ 0

Допустим, данный список имеет поле size, хранящее размер, и методы для вычитывания узла списка по индексу Node<T> getNode(int index) и удаления узла removeNode(Node<T> node), тогда перемешивание исходного массива можно реализовать так:

создать новый список
сгенерировать случайный индекс для размера исходного списка
взять значение узла в новый список
удалить узел из исходного списка, уменьшив размер исходного списка
повторять, пока исходный список не станет пустым
переприсвоить содержимое нового списка

Основной метод перемешивания:

public void shuffle() {
    SingleLinkedList<T> tmp = new SingleLinkedList<>();
    Random r = new Random();

    while (size > 0) {
        Node<T> curr = getNode(r.nextInt(size));
        tmp.add(curr.data);
        removeNode(curr);
    }
    
    this.head = tmp.head;
    this.tail = tmp.tail;
    this.size = tmp.size;
}

Методы для получения и удаления узлов:

public Node<T> getNode(int i) {
    if (i < 0 || i >= size) {
        throw new IndexOutOfBoundsException("Invalid index " + i + " for the list of size = " + size);
    }
    Node<T> res = head;
    while (i > 0) {
        res = res.next;
        i--;
    }
    return res;
}

public void removeNode(Node<T> node) {
    Node<T> prev = null;
    Node<T> curr = head;
    while (curr != node && curr != null) {
        prev = curr;
        curr = curr.next;
    }
    if (curr != null) {
        if (prev == null) { // removing head
            head = head.next;
        } else {
            prev.next = curr.next;
        }
        this.size--;
    }
}

Остальной код класса SingleLinkedList<T>:

public class SingleLinkedList<T> {
    static class Node<T> {    
        T data;    
        Node<T> next;    
            
        public Node(T data) {    
            this.data = data;    
            this.next = null;    
        }    
    }    
     
    private Node<T> head = null;
    private Node<T> tail = null;
    private int size = 0;
        
    public SingleLinkedList<T> add(T data) {
        Node<T> newNode = new Node<>(data);
            
        if (head == null) {  // list empty
            head = tail = newNode;
        }    
        else {    
            tail = tail.next = newNode;    
        }
        size++;
        return this;
    }

    public SingleLinkedList<T> addAll(T ... data) {
        for (T d : data) {
            add(d);
        }
        return this;
    }    
       
    @Override 
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size: ").append(this.size).append(" [");
        boolean fst = true;
        for (Node<T> curr = head; curr != null; curr = curr.next) {
            if (fst) {
                fst = false;
            } else {
                sb.append(", ");
            }
            sb.append(curr.data);
        }
        sb.append(']');
        return sb.toString();
    }
    
    // public Node<T> getNode(int i) {...}
    // public void removeNode(Node<T> node) {...}
    // public void shuffle() {...}
}

Тесты:

SingleLinkedList<Integer> sll = new SingleLinkedList<>();

sll.addAll(1, 7, -2, 10, 0, -5, 12, -1);

System.out.println(sll);
for (int i = 0; i < 4; i++) {
    sll.shuffle();
    System.out.println("Shuffle #" + (i + 1) + ": " + sll);
}

Результаты:

size: 8 [1, 7, -2, 10, 0, -5, 12, -1]
Shuffle #1: size: 8 [7, 10, 12, -1, -5, -2, 0, 1]
Shuffle #2: size: 8 [-2, 1, 7, -1, 12, 0, 10, -5]
Shuffle #3: size: 8 [12, 7, -2, 0, -1, 10, -5, 1]
Shuffle #4: size: 8 [-5, -2, 7, 0, 1, -1, 12, 10]

Как написать метод перемешивания своего LinkedList^a на Java

Ответы