Создание кругового связанного списка и нахождение начала цикла - PullRequest
Новая
       10

Создание кругового связанного списка и нахождение начала цикла

0 голосов
/ 04 мая 2018

Мое задание - найти начало цикла в круговом связанном списке. Поскольку список не предоставлен, я решил сделать вывод, получив пользовательский ввод для размера списка, а затем запустить цикл for с таким размером. Самый последний вход (последний узел) будет указывать где-то в связанном списке, чтобы создать цикл. Моя функция для создания связанного списка работает, если я получаю данные head-> data при получении ввода от пользователя, он печатает правильное значение, но когда я вызываю функцию main, указатель head указывает на NULL, и я получаю сегментацию неисправность. Может кто-нибудь взглянуть на мой код и объяснить, почему происходит что-то подобное? 

#include <iostream>

using namespace std;

struct node{

    int data;
    node *next;
};

node *head = NULL;
node *tail = NULL;
node *slow = NULL;
node *fast = NULL;

int findLoop(node * head);
void getList(node * head, int listSize);
bool isEmpty(node * head);

int main(){
int listSize;
    cout <<"\nEnter the size of the list: ";
    cin >> listSize;

getList(head, listSize);
if(head != NULL){
cout << "\n\n\nprinting head " << head->data; //Seg Fault
}
else{
    cout << "Head is NULL" << endl;
}
findLoop(head);

    return 0;
}

int findLoop(node *head){
    slow = head;
    fast = head;
    if(head == NULL){
        cout << "\nThe list is empty\n";
    }
    bool isLoop = false;
    while(slow != NULL && fast != NULL){ 
        if(slow == fast && isLoop == false){
            slow = head;
            isLoop = true;
        }
        else if(slow == fast && isLoop == true){
            cout <<"\nThe loop starts at: ";
            return slow->data;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    cout <<"\nThere is no loop\n";
    return 0;
}
void getList(node * head, int listSize){

    int userData;
    for(int i=0; i<listSize; i++){
        node *temp = new node;
        cout <<"\nEnter a number: ";
        int NodeValue = 0;
        cin >> NodeValue;
        temp->data = NodeValue;
        if(head == NULL){   
            head = temp;
            cout << head->data << endl; //Test for appropriate pointing.
        }
        if(tail != NULL){
            tail->next = temp;// point to new node with old tail
        }
        tail = temp;// assign tail ptr to new tail
        temp->next = tail;
        if(i == listSize-1){
            node *temp2;
            temp2 = head;
            int iNumber = rand() % i;
            for(int j=0; j<iNumber; j++){
                temp2 = temp2->next;
            }
            tail->next = temp2;
        }
    }
}

1 Ответ

0 голосов
/ 04 мая 2018

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

 void getList(node*&, int );

или лучше определить тип указателя 

 using nodePtr = node*;

 void getList(nodePtr&, int);
...