美文网首页算法的阶梯
Even and odd linked list

Even and odd linked list

作者: Tedisaname | 来源:发表于2018-08-29 15:07 被阅读9次

    Even and odd list
    Given a single linked list, put all the odd and even nodes together. Note >that the odd and even nodes here refer to the parity of the node number, >not the parity of the value of the node.

    // C codes:
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>    //function to exit()
    #define OK 1    //status for 1
    #define ERROR 0 //status for 0
    
    //struct for a node
    typedef struct Node{
        int data;
        struct Node * next;
    }Node,*PNode;
    
    // Function to the linked list initialization 
    int Initialization(PNode& head)
    {
        head = (PNode)malloc(sizeof(Node));//create a head Node
        head->next = NULL;//initialize the head node
        return OK;
    }
    
    
    //crerate the linked list from user input
    void create(PNode head)
    {
    
        int m,a;
        PNode p, q;
        printf("Please input the length of the linked list:");
        scanf("%d",&m); 
        q = NULL;
        for(int i = 0; i < m; i++)
        {
            scanf("%d",&a);
            p = (PNode)malloc(sizeof(Node));
            p->data = a;
            p->next = NULL;
            if(head->next == NULL)//attention!!!!head ->next == NULL ,not head == NULL
            head->next = p;//head directly points to p if the head points to NULL 
            else
            q->next = p;//else,pointer q points to the p;
            
            q = p;//pointer q points to p   
        }
            
    }
    
    
    //print all the emements of linked list
    void printLinkedlist(PNode head)
    {
        PNode t = head->next;//the next field of the head pointer is the first valid node attention~!!!!!!
        while(t != NULL)
        {
            printf("%d ",t->data);
            t = t->next;
        }
        printf("\n");
    }
    //Function to get the length of the linked list
    int getlength(PNode head)
    {
        int k = 0;
        PNode t = head->next;
        while(t != NULL)
        {
            k++;
            t = t->next;
        }
        return k;
    }
    //Function to the even and odd linked list
    PNode evenOddList(PNode A,PNode result,int len)
    {
        int j = 1;
        PNode p,q,w; 
        p = A->next;
        q = NULL;
        
        while(p != NULL && j <= len)
        {
            
            if(j % 2 == 1)
            {
                 PNode w = (PNode)malloc(sizeof(Node));
                 w->data = p->data;
                 w->next = NULL;
                if(result->next == NULL)
                    result->next = w;
                else
                    q->next = w;
                
                q = w;  
            }
            j++;
            p = p->next;
        }
        
        j = 1; 
        p = A->next;
        while(p != NULL && j <= len)
        {
            
            if(j % 2 == 0)
            {
                 PNode w = (PNode)malloc(sizeof(Node));
                 w->data = p->data;
                 w->next = NULL;
                if(result->next == NULL)
                    result->next = w;
                else
                    q->next = w;
                
                q = w;  
            }
            j++;
            p = p->next;
        }
        
        return result;
    }
    
    int main()
    {
        PNode A,result;//create two nodes of two linked list A and result
        if(Initialization(A)){
            printf("Initialization successful!\n");
        }
        else
        {
            printf("Initialization failed!\n"); 
            exit(ERROR);
        }   
        create(A);//Create linked list from the function to  user input
        
        printLinkedlist(A);//print list before sorting  
        
        int len = getlength(A);//get the length of the linked list
        
        printf("the length of the linked list is %d\n",len);
        
        if(Initialization(result)){
            printf("Initialization successful!\n");
        }
        else
        {
            printf("Initialization failed!\n"); 
            exit(ERROR);
        }   
        
        evenOddList(A,result,len);//Function is called to create the even and odd linked list
        printLinkedlist(result);//print the linked list of the even and
        return 0;
    }
    

    driver data to test:
    input: 1->2->3->4->5->NULL
    output: 1->3->5->2->4->NULL

    You can leave me a message if you find out anything incorrect in my diary, I'll correct it, thanks.

    相关文章

      网友评论

        本文标题:Even and odd linked list

        本文链接:https://www.haomeiwen.com/subject/xetkwftx.html