Не выводит положительные числа. Односвязный список

Question

Не выводит положительные числа. Односвязный список

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

В моем односвязном списке сортируются элементы в таком порядке: отрицательные, нулевые и положительные.

Проблема в том, что положительные элементы не выводятся, когда отрицательные и нулевые выводятся в полном порядке. К примеру, есть массив int[] arr = {0,-1,2,9}, его элементами я заполняю свой односвязный список, выводится [-1,0], хотя должно быть так: [-1,0,2,9].

Прилагаю метод, в котором реализуется сортировка, полагаю, что ошибка в нем. Решаю через три других списка, для каждого свои элементы.

public void rearrangeList()throws SimpleLinkedListException {
            if (head == null || head.next == null) {
                return;
            }
        SimpleLinkedListNode<T> minusHead = null; // голова списка отрицательных элементов
        SimpleLinkedListNode<T> minusTail = null; // хвост списка отрицательных элементов
        SimpleLinkedListNode<T> zeroHead = null; // голова списка нулевых элементов
        SimpleLinkedListNode<T> zeroTail = null; // хвост списка нулевых элементов
        SimpleLinkedListNode<T> plusHead = null; // голова списка положительных элементов
        SimpleLinkedListNode<T> plusTail = null; // хвост списка положительных элементов
        SimpleLinkedListNode<T> current = head;
            while (current != null) {
                SimpleLinkedListNode<T> next = current.next;
                current.next = null; // отсоединяем текущий элемент от списка
                if ((Integer)current.value < 0) {
                    if (minusHead == null) {
                        minusHead = current;
                    } else {
                        minusTail.next = current;
                    }
                    minusTail = current;
                }
                if ((Integer)current.value == 0) {
                    if (zeroHead == null) {
                        zeroHead = current;
                    } else {
                        zeroTail.next = current;
                    }
                    zeroTail = current;
                }
                if ((Integer)current.value > 0){
                    if (plusHead == null) {
                        plusHead = current;
                    } else {
                        plusTail.next = current;
                    }
                    plusTail = current;
                }
                current = next;
            }

            if (minusHead != null) {
                head = minusHead;
                minusTail.next = zeroHead != null ? zeroHead : plusHead;
            } else if (zeroHead != null) {
                head = zeroHead;
                zeroTail.next = plusHead;
            } else {
                head = minusHead;
            }
        }

java сортировка односвязный-список

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

Answer 1

▲ 0

Добавил исключения для случаев когда только положительные элементы и элементы всех трех типов.

if (minusHead != null) {
            head = minusHead;
            if (zeroHead != null) {
                minusTail.next = zeroHead;
                zeroTail.next = plusHead;
            } else {
                minusTail.next = plusHead;
            }
        } else if (zeroHead != null) {
            head = zeroHead;
            zeroTail.next = plusHead;
        } else {
            head = plusHead;
        }

Answer 2

▲ 0

Проще переписать с нуля, создав метод add и используя списки целиком в методе rearrange:

    public void rearrange() {
        SingleLinkedList<T> neg = null;
        SingleLinkedList<T> zer = null;
        SingleLinkedList<T> pos = null;
        
        for (Node<T> curr = head; curr != null; curr = curr.next) {
            if (curr.data.doubleValue() < 0) {
                if (neg == null) neg = new SingleLinkedList<>();
                neg.add(curr.data);
            } else if (curr.data.doubleValue() == 0) {
                if (zer == null) zer = new SingleLinkedList<>();
                zer.add(curr.data);
            } else {
                if (pos == null) pos = new SingleLinkedList<>();
                pos.add(curr.data);
            }
        }
        this.head = null;
        this.tail = null;
        if (neg != null) {
            this.head = neg.head;
            this.tail = neg.tail;
        }
        if (zer != null) {
            if (this.head == null) {
                this.head = zer.head;
            } else {
                this.tail.next = zer.head;
            }
            this.tail = zer.tail;
        }
        if (pos != null) {
            if (this.head == null) {
                this.head = pos.head;
            } else {
                this.tail.next = pos.head;
            }
            this.tail = pos.tail;
        }
    }

// основной код класса
class SingleLinkedList<T extends Number> {
    class Node<T> {    
        T data;    
        Node<T> next;    
            
        public Node(T data) {    
            this.data = data;    
            this.next = null;    
        }    
    }    
     
    public Node<T> head = null;    
    public Node<T> tail = null;    
        
    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;    
        }
        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('[');
        for (Node<T> curr = head; curr != null; curr = curr.next) {
            if (sb.length() > 1) {
                sb.append(", ");
            }
            sb.append(curr.data);
        }
        sb.append(']');
        return sb.toString();
    }
    // public void rearrange() {...}
}

Тесты:

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

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

System.out.println(sll);
sll.rearrange();
System.out.println(sll);

Результат:

[1, 0, -2, 10, 0, -5, 12, -1]
[-2, -5, -1, 0, 0, 1, 10, 12]

Результаты других тестов:

[1, 10, 2, 0, 5, 0, 12]
[0, 0, 1, 10, 2, 5, 12]

[-1, -10, 2, 10, 5, 20, -12]
[-1, -10, -12, 2, 10, 5, 20]

[-1, -10, -2, 0, -5, 0, -12]
[-1, -10, -2, -5, -12, 0, 0]

Не выводит положительные числа. Односвязный список

Ответы