0

我的代码是关于检测链表中的循环/循环，然后删除错误。但是，在运行代码以删除循环/循环后，仅打印链表的第一个元素。

我已经尝试合并 detectCycle() 和 removeCycle() 函数，但它对输出没有影响。

class ListElem
{
public:
    int value;
    ListElem *next;   //Pointer used to make link
};


int length(ListElem *head)   //function to check length of linked list
{
    int len = 0;
    while(head != NULL)
    {
        head = head -> next;
        len += 1;
    }
    return len;
}



void insertAtTail(ListElem *&head, ListElem *elem)    //if the list is non - empty, the insertAtTail algorithm
                                                        //does not change the head of the list
{
    ListElem *lastElem;   //lastElem will point to the last element

    if ( head == NULL ) // Detect and handle exception case....    (in case the list is empty)
   {
      head = elem;
      elem->next = NULL;
   }

   else
   {
       lastElem = head;

        while(lastElem->next != NULL)     //Find the last element in the list

        {

            lastElem = lastElem->next;

        }

        lastElem->next = elem;   // Link "elem" to lastElem:
        elem->next = NULL;      // Mark new elem as the last element:

    }
}

void buildList(ListElem *&head)
{
    int data;   // data = the value of elements to be inserted in linked list that will be input by the user
    cin>>data;
    ListElem *p;


    while (data != -1)    // when the user inputs '-1', the process of taking input will stop
    {
        p = new ListElem;
        p -> value = data;

        insertAtTail(head, p);
        cin>>data;
    }
}

void Print(ListElem *head)
{
   ListElem *p;

   p = head;             // Very important: start at first element

   cout << "List ==> ";
   while ( p != NULL )
   {
      cout << p->value << "  ";  // Access value stored in list element
      p = p->next;               // Visit next element in list
   }
   cout << "\n\n";
}


void removeCycle(ListElem *head, ListElem *fast)
{
    ListElem *slow = head;

    while(slow ->next != fast -> next)   // ensures that slow pointer does not go past the fast pointer, and detects the
    {                           // node at which slow and fast pointers point to the same node
        slow = slow -> next;
        fast = fast -> next;
    }


    fast -> next = NULL;   // This works when the end of the loop is reached and the “next” pointer to that node
                            //is made NULL representing the end of a linked list without loop


}

bool detectCycle(ListElem *head)
{
    ListElem *slow = head;
    ListElem *fast = head;


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

        if(fast == slow)
        {
            removeCycle(head, fast);  // this will call the remove cycle function to remove the cycle. The position
                                    // of the fast pointer is to be retained, 
 so it is passed as argument to the
            return true;               // remove cycle function
        }
    }
       return false;
}
int main()
{
    ListElem *head = NULL;

    buildList(head);

    /* Deliberately create a loop/cycle for testing */
    head->next->next->next->next->next = head->next->next->next;

    if(detectCycle(head))
    {
        cout<<"A loop was present, and has been removed. List after removal of loop is :"<<endl<<endl;

        Print(head);
    }
    else
    {
        cout<<"A loop was not present"<<endl;
        Print(head);

    }

    cout<<"The length of the list is : "<<length(head);
    cout<<endl<<endl;
    return 0;
}

我希望 Print() 函数输出整个更正的列表。

4

0 回答 0