Алгоритм Вопрос, связанный с Linkedlist - PullRequest
Новая
       4

Алгоритм Вопрос, связанный с Linkedlist

0 голосов
/ 08 апреля 2020

Я пытаюсь вернуть средний узел из односвязного списка, и вот как я подхожу, но здесь я получаю Nullpointexception. Кто-нибудь может объяснить, где я ошибаюсь? 

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
    ListNode slow = head; 
    ListNode fast = head;
        if (slow == null) {
            return null;
        }
        if (slow.next.next == null) {
            return slow.next;
        }
        while (slow.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

1 Ответ

0 голосов
/ 09 апреля 2020

Я считаю, что в этом коде нет ошибок.

Я только что запустил ваш код со связанным списком, который выглядит как 1->2->3->4->5, как вы указали в комментариях, и он работает просто отлично.

Кроме того, это вопрос от LeetCode , и код, который вы разместили, проходит все тестовые примеры. На самом деле этот код выглядит идентично третьему решению, которое там представлено (что можно увидеть, нажав на вкладку «решение»).

После редактирования:

Причина, по которой вы получаете исключение нулевого указателя в обновленном коде, заключается в том, что вы не проверяете, является ли fast.next нулевым, до доступа к fast.next.next. Таким образом, если вы измените условие while-l oop с while (slow.next != null && fast.next.next != null) на while (slow.next != null && fast.next != null && fast.next.next != null), то избавитесь от исключения нулевого указателя.

Однако это все равно приведет к вынесению вердикта Неправильный ответ, поскольку ваш алгоритм неверен.

Вы не должны проверять, являются ли fast.next и fast.next.next ненулевыми, но вместо этого вы должны проверять, являются ли fast и fast.next нулевыми , Я предлагаю вам разобраться с этим на бумаге, чтобы понять, почему (опубликованный вами код не будет работать для 1->2->3->4->5->6, ответ на который должен быть ListNode 3). Обновленный код с этими изменениями представлен ниже: 

class Solution {
    public ListNode middleNode(ListNode head) {
    ListNode slow = head; 
    ListNode fast = head;
        if (slow == null) {
            return null;
        }

        if (slow.next == null) {
            return slow;
        }

        while (slow.next != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
...