2022-07-22 回顾链表操作以及部分问题

/* File: linked.cpp Function: 回顾链表的一些操作，查找单向倒数N节点、公共节点、是否闭环、链表的反转 Writer: syq Time: 2022-07-22 */

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


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

/* 初始化链表,返回头指针 */

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;   //赋个值吧
       
    }
    return phead;
}


/* 销毁链表 */

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;
}


/* 打印链表 */

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. 单向链表如何查找倒数第N个节点 通常的做法是遍历一边得到长度，然后遍历第二遍，取得对应元素。 这种做法时间消耗是链表长度的2倍 - N。 使用快慢指针，结合步长实现 1 2 3 4 5 7 8 9 */


struct link_node* ReserverFind(struct link_node*  plinkhead,int npos)
{
    
    //当前指针
    struct link_node* pleft = plinkhead;
    struct link_node* pright = plinkhead;
    //遍历，找到最后一个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.链表的反转（原地反转） 需要一个prev指针遍历的同时，成为前指针； 需要一个临时指针存放next;需要一个当前指针做遍历 */

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.判断链表有没有环 慢指针往后面移动一个节点，快指针每一次移动两个 方法一，遍历，看下指针是否有重复 方法二，使用快慢指针，指针1每次移动1个，指针2每次移动2个，当有环时候，指针1和指针2总会相遇 */


bool hasCycle(struct link_node *head) {
    
    struct link_node* slow = head;
    struct link_node* fast = head;
    //如果没有环，则快指针一路到头，解决问题；
    //如果有环，则两人总会相遇
    while((fast != NULL) && (fast->pnext != NULL)){
    
        slow = slow->pnext;
        fast = fast->pnext->pnext;
        if(slow == fast){
    
            return true;
        }
    }
    return false;
}


/* 4.判断两个链表有没有公共节点 1.如果Len1 = len2 ,直接遍历比较 2.如果Len1 != len2，我们应该先让长的链表从表头“走” len1 - len2步 一旦有节点重合，则长度是一样的 */



int main(int argc,char* argv[])
{
    
    struct link_node* phead = Initlinknode(10);
    Printlinknode(phead);
    //查找倒数第2个节点
    std::cout<<ReserverFind(phead,2)->value<<std::endl;

     //查找倒数第4个节点
    std::cout<<ReserverFind(phead,4)->value<<std::endl;


     //查找倒数第6个节点
    std::cout<<ReserverFind(phead,6)->value<<std::endl;

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

    getchar();
    DeInitlinknode(pnewhead);

    
    
    return 0;
}