Выяснение, является ли связанный список четной или нечетной длины - PullRequest
Новая
       33

Выяснение, является ли связанный список четной или нечетной длины

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

Я хочу выяснить, является ли связанный список нечетной или четной длины.

У меня есть указатель, который перемещается с удвоенной скоростью.Если длина связанного списка четная, быстрый указатель в конечном итоге достигнет нуля.Если длина связанного списка нечетная, быстрый указатель достигнет конца; 

    //Method 1  Works

    int isLengthEvenOrOdd(struct Node* head){
         Node *fast;
         fast=head;

         if(head==NULL)
            return 0;

         while(fast && fast->next!=NULL){
             fast=fast->next->next;
         }

         if(fast==NULL)
            return 0;
         else
            return 1;
    }


    //Method 2  Segmentation Fault

    int isLengthEvenOrOdd(struct Node* head){
         Node *fast;
         fast=head;

         if(head==NULL)
            return 0;

         while(head && fast->next!=NULL){
             fast=fast->next->next;
         }

         if(fast==NULL)
            return 0;
         else
            return 1;
    }

Может кто-нибудь сказать мне, почему приведенный ниже код неправильный? 

while(head && fast->next!=NULL){
         fast=fast->next->next;
     }

Ответы [ 2 ]

3 голосов
/ 20 июня 2019

Внимательно посмотрите на эти две инструкции (я предполагаю, что между ними нет ничего) 

     if(head==NULL)
        return 0;

     while(head && fast->next!=NULL){
         fast=fast->next->next;
     }

head никогда не будет NULL в условии while(), поэтому вы всегда проверяете только fast->next.Как только вы дойдете до конца, fast будет иметь значение NULL, и вы получите ошибку сегментации.

Предложение, не поймите это неправильно, получите хорошую IDE (есть много бесплатных) и узнайте, какиспользовать отладчик.Если вы хотите стать более хардкорным, продолжайте использовать текстовый редактор и используйте gdb или любой другой отладчик, который вы предпочитаете.Ваша производительность увеличится.

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

Давайте посмотрим на эту часть кода: 

while(head && fast->next!=NULL){
    fast=fast->next->next;
}

голова никогда не будет нулевой

теперь скажем, что список равен 1 -> 2 -> 3 -> 4-> быстро с нулевой головой после 1-й итерации 1 -> 2 -> 3 -> 4 -> быстро с нулевой головой

теперь смотрите в соответствии с кодом fast-> next не является нулевым, поэтому оно входит в цикл 

and sets fast to "fast->next-> next"
which makes
fast = null as

1 -> 2 -> 3 -> 4 -> null 
head
                    fast

Таким образом, когда вы пытаетесь получить доступ к «следующему» из null, вы сталкиваетесь с ошибкой сегментации

Code1 работает из-за условия fast && fast-> next

, так как высначала проверяем существование fast, вы никогда не пытались получить доступ к тому, чего не было.Код вышел из цикла только на fast = null, чего не было в Code2

...