Блог

Главная - Вопросы по программированию - Рекурсивное обращение связанного списка в java с использованием переменной temp

Рекурсивное обращение связанного списка в java с использованием переменной temp

#java #linked-list

#java #связанный список

Вопрос:

Я реализовал решение для обращения связанного списка в java, которое я нашел в Интернете. Но по какой-то причине это не работает в моем коде.

Когда я печатаю список, он печатает только первый узел. Я знаю, что метод print работает, потому что он печатает все целиком, когда я не пытаюсь изменить.

Где я ошибся в этом коде?

 public class LinkedLists {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addLast(10);
        list.addLast(20);
        list.addLast(30);
        list.reverseList();
        list.print();
    }
    
    
    public static class LinkedList{
        private class Node{
            private int value;
            private Node next;
        }
            public Node first;
            public Node last;
    
    public void addLast(int item){
        Node node = new Node();
        node.value = item;
            if(first == null) {
                first = node;
                last = node;
                } else {
                last.next = node;
                last = node;
                }
            }
            private Node reverse(Node head, Node newHead) {
                //base case: when first = last you return
                if(head == null) {
                    return newHead;
                }
                Node temp = head.next;
                head.next = newHead; //this will initially be null
                newHead = head;
                head = temp;
                return reverse(head, newHead);
            }
            
            public Node reverseList() {
                return reverse(first, null);
            }
            
            public void print(){
                Node current = first;
                while (current != null){
                    System.out.print(current.value   " ");
                    current = current.next;
                } 
            }
        } //class ends
    }

Комментарии:

1. Ваш обратный алгоритм никогда не затрагивает важные элементы first и last , но ваш print метод начинается с first (который был первым и, предположительно, теперь является последним).

2. сначала передается в reverse через reverseList

3. В качестве значения, да. Но это не значит, что first last они обновляются. Естественно, если вы изменили список, их нужно будет поменять местами. Причина, по которой вы видите только одно напечатанное значение, заключается в том, что first оно указывает на последнюю запись после разворота.

Ответ №1:

Хотя reverse возвращает правильную ссылку для нового заголовка, начальный вызов reverseList — в основной программе — игнорирует эту возвращенную ссылку.

Ваш reverseList метод должен лучше ничего не возвращать, а вместо этого обновлять элементы first and last :

 public void reverseList() {
    last = first;
    first = reverse(first, null);
}