2022-07-22 review linked list operation and some problems

/* File: linked.cpp Function:  Review some operations of the linked list , Find one-way reciprocal N node 、 Public nodes 、 Closed loop 、 Reverse of linked list  Writer: syq Time: 2022-07-22 */

#include <stdio.h>
#include <iostream>


struct link_node
{
    
    int value;
    struct link_node*   pnext;
   
};

/*  Initialize linked list , Return head pointer  */

struct link_node* Initlinknode(int nsize)
{
    
    struct link_node* phead = (struct link_node*)malloc(sizeof(struct link_node));
    std::cout<<"malloc:"<<phead<<std::endl;
    phead->pnext = nullptr;
    phead->value  = 1;
    struct link_node* pcurrnt = phead;
    for(int i = 0; i < nsize-1; i ++)
    {
    
        pcurrnt->pnext  = (struct link_node*)malloc(sizeof(struct link_node));
         std::cout<<"malloc:"<<pcurrnt->pnext<<std::endl;
        pcurrnt = pcurrnt->pnext;
        pcurrnt->pnext = nullptr;
        pcurrnt->value = i;   // Give it a value 
       
    }
    return phead;
}


/*  Destroy the list  */

struct link_node* DeInitlinknode(struct link_node* phead)
{
    
   struct link_node* pcur = phead;
   while(pcur->pnext != nullptr)
   {
    
        free(pcur);
        std::cout<<"free:"<<pcur<<std::endl;
        pcur = pcur->pnext;
   }
   free(pcur);
   std::cout<<"free:"<<pcur<<std::endl;
}


/*  Print linked list  */

struct link_node* Printlinknode(struct link_node* phead)
{
    
   struct link_node* pcur = phead;
   for(pcur; pcur->pnext != nullptr; pcur = pcur->pnext)
   {
    
        std::cout<<pcur->value<<" ";
   }
   std::cout<<pcur->value<<std::endl;
}


/* 1.  How to find the penultimate in a one-way linked list N Nodes   The usual way is to traverse one side to get the length , Then traverse the second time , Get the corresponding element .  The time consumption of this practice is the length of the linked list 2 times  - N.  Use the speed pointer , Combined with step size  1 2 3 4 5 7 8 9 */


struct link_node* ReserverFind(struct link_node*  plinkhead,int npos)
{
    
    // Pointer to the current 
    struct link_node* pleft = plinkhead;
    struct link_node* pright = plinkhead;
    // Traverse , Find the last one 2N
    for(;pleft;pleft = pleft->pnext)
    {
    
       pright = pleft;
       for(int i = 0; i < npos; i ++)
       {
    
            pright = pright->pnext;
       }
       if(pright == nullptr)
        break;
    }
    return pleft;
}


/* 2. Reverse of linked list （ Reverse in place ）  Need one prev While traversing the pointer , Become the front pointer ;  Need a temporary pointer to store next; You need a current pointer to traverse  */

struct link_node* Reverse_list(struct link_node* phead)
{
    
    struct link_node* prev = nullptr;
    struct link_node* pcurrnt = phead;


#if 1
    while(pcurrnt)
    {
    
        struct link_node*pnode = pcurrnt->pnext;
        pcurrnt->pnext = prev;
        prev = pcurrnt;
        pcurrnt = pnode;
    }
#endif
    return prev;
}



/* 3. Judge whether there are links in the linked list   The slow pointer moves a node backward , The fast pointer moves two at a time   Method 1 , Traverse , Check whether the pointer repeats   Method 2 , Use the speed pointer , The pointer 1 Each move 1 individual , The pointer 2 Each move 2 individual , When there is a ring , The pointer 1 And a pointer 2 There's always a meeting  */


bool hasCycle(struct link_node *head) {
    
    struct link_node* slow = head;
    struct link_node* fast = head;
    // If there is no ring , Then the fast pointer goes all the way to the end , solve the problem ;
    // If there are rings , Then two people will always meet 
    while((fast != NULL) && (fast->pnext != NULL)){
    
        slow = slow->pnext;
        fast = fast->pnext->pnext;
        if(slow == fast){
    
            return true;
        }
    }
    return false;
}


/* 4. Determine whether the two linked lists have common nodes  1. If Len1 = len2 , Direct traversal comparison  2. If Len1 != len2, We should first let the long linked list from the header “ go ” len1 - len2 Step   Once a node coincides , Then the length is the same  */



int main(int argc,char* argv[])
{
    
    struct link_node* phead = Initlinknode(10);
    Printlinknode(phead);
    // Look for the last 2 Nodes 
    std::cout<<ReserverFind(phead,2)->value<<std::endl;

     // Look for the last 4 Nodes 
    std::cout<<ReserverFind(phead,4)->value<<std::endl;


     // Look for the last 6 Nodes 
    std::cout<<ReserverFind(phead,6)->value<<std::endl;

    // reverse 
    struct link_node* pnewhead = Reverse_list(phead);
    Printlinknode(pnewhead);

    getchar();
    DeInitlinknode(pnewhead);

    
    
    return 0;
}