用快慢指针原理得到单链表中间结点的数据

不念不忘少年蓝@ 2022-05-20 07:39 158阅读 0赞

普通方法是遍历一遍得到表长，再根据此值移到中间  
快慢指针的方法可以提高效率，当快指针以两倍速度到达表尾时慢一些的指针刚好在中间结点

#include<stdio.h>
    #include<stdlib.h>
    #include<stddef.h>
    #define Num_Count 6//数据结点个数
    //求单链表的中间结点数据值。创建随机数单链表/显示链表内容/获取中间结点数据值/退出/小甲鱼模版
    typedef struct List_Node{
        int data;
        struct List_Node *next;
    }Forward_List_Node;
    
    Forward_List_Node* List_1;
    unsigned exist = 0;
    void Create_List(int length)
    {
        List_1 = (Forward_List_Node*)malloc(sizeof(Forward_List_Node));
        Forward_List_Node* newNode=(Forward_List_Node*)malloc(sizeof(Forward_List_Node));
        Forward_List_Node* curNode=newNode;
        newNode->data = rand()%100+1;
        List_1->next=curNode;
        curNode->next = NULL;
        int index;
        for(index=1;index<length;index++)
        {
            newNode = (Forward_List_Node*)malloc(sizeof(Forward_List_Node));
            newNode->data = rand()%100+1;
            curNode->next = newNode;
            curNode = newNode;
            curNode->next = NULL;
        }
        printf("创建成功\n");
        exist = 1;
        system("pause");
    }
    void displaymenu()
    {
        int choice;
        system("cls");
        printf("1.创建一个由随机数构成的链表\n");
        printf("2.顺序显示链表所有数据\n");
        printf("3.获取并显示中间结点的数据值\n");
        printf("0.退出程序\n");
        printf("输入对应数字选择功能: ");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:Create_List(Num_Count);displaymenu();break;
            case 2:if(exist)PrintItsNodes();displaymenu();break;
            case 3:if(exist)printf("%d\n",GetMiddleNodedata());system("pause");displaymenu();break;
            default:break;
        }
    }
    void PrintItsNodes()
    {
        Forward_List_Node *cur = List_1->next;
        while(cur)
        {
            printf("%-4d",cur->data);
            cur=cur->next;
        }
        printf("\n");
        system("pause");
    }
    int GetMiddleNodedata()
    {
        Forward_List_Node *mid,*faster;
        if(Num_Count%2)mid=List_1->next,faster = List_1->next;
        else mid=List_1,faster = List_1;
        while(faster->next)
        {
            faster=faster->next->next;
            mid = mid->next;
        }
        return mid->data;
    }
    int main()
    {
        //printf("\t\t取单链表中间结点数据的程序");
        srand((unsigned)time(0));
        displaymenu();
        //printf("%d\n",time(NULL));
        return 0;
     }