Невозможно удалить первый узел из класса связанного списка - PullRequest
Новая
       18

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

0 голосов
/ 27 июня 2019

У меня есть проблема.Я использую учебник Cracking the Coding Interview, чтобы попрактиковаться в некоторых вопросах интервью со связанными списками, и я попытался реализовать собственную структуру данных LinkedList, прежде чем решить проблему.Я пытался проверить функциональность класса.Все остальное прекрасно работает, но я не могу понять, как удалить первый узел LinkedList.

Убедившись, что моя собственная реализация кода не работает, я попробовал код из книги CTCI, но безрезультатно.Ниже приведен код структуры данных моего связанного списка: 

static class Node{
        Node next = null;
        int data;

        public Node(int d) {
            data = d;
        }

        void appendToTail(int d) {
            Node end = new Node(d);
            Node n = this;
            while(n.next != null) {
                n = n.next;
            }
            n.next = end;
        }

        Node deleteNode(Node head, int d) {
            if(head == null) return null;
            Node n = head;
            if(n.data == d) {
                return head.next;
            }

            while(n.next != null) {
                if(n.next.data == d) {
                    n.next = n.next.next;
                    return head;
                }
                n = n.next;
            }
            return head;

        }

        int size () {
            int length = 0;
            Node n = this;
            if(n == null) {
                return 0;
            } 
            length = 1;
            while(n.next != null) {
                n = n.next;
                length++;
            }

            return length;
        }

        void printNode() {
            Node d = this;
            while(d != null) {
                if(d.next != null) {
                    System.out.print(d.data + " --> ");
                } else {
                    System.out.println(d.data + " ");
                }

                d = d.next;
            }
        }

    }

Мне было интересно, почему я смог удалить все остальные узлы, кроме первого.

Я установил следующий тестовый пример: 

public static void main(String[] args) {
        //test cases
        Node test = new Node(0);
        for(int i = 1; i <= 20; i++) {
            test.appendToTail(i);
        }

        test.printNode();

        for(int i = 0; i <= 20; i = i + 2) {
            test.deleteNode(test, i);
        }

        test.printNode();


    }

Вывод, полученный после удаления всех четных узлов, равен 0 --> 1 --> 3 --> 5 --> 7 --> 9 --> 11 --> 13 --> 15 --> 17 --> 19, но ожидаемый вывод - 1 --> 3 --> 5 --> 7 --> 9 --> 11 --> 13 --> 15 --> 17 --> 19.

1 Ответ

2 голосов
/ 27 июня 2019

Проблема в том, что при удалении первого элемента в связанном списке вы отправляете head.next, но не используете его в тестовой переменной.

Код должен быть 

public static void main(String[] args) {
        //test cases
        Node test = new Node(0);
        for(int i = 1; i <= 20; i++) {
            test.appendToTail(i);
        }

        test.printNode();

        for(int i = 0; i <= 20; i = i + 2) {
            test = test.deleteNode(test, i);
        }

        test.printNode();


    }

добавить это 

test = test.deleteNode(test, i);

Тогда результат будет 

0 --> 1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 10 --> 11 --> 12 --> 13 --> 14 --> 15 --> 16 --> 17 --> 18 --> 19 --> 20
3 --> 5 --> 7 --> 9 --> 11 --> 13 --> 15 --> 17 --> 19
...