师--链表的结点插入

墨蓝 2022-06-18 02:39 161阅读 0赞

think:  
1链表的结点的头部插入+链表的结点的中间插入+链表的结点的尾部插入

[sdut题目链接][sdut]

师–链表的结点插入  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
给出一个只有头指针的链表和 n 次操作，每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。

Input  
多组输入。每组数据首先输入一个整数n(n∈\[1,100\])，代表有n次操作。  
接下来的n行，每行有两个整数Mi(Mi∈\[0,10000\])，Xi。

Output  
对于每组数据。从前到后输出链表的所有元素,两个元素之间用空格隔开。

Example Input  
4  
1 1  
1 2  
0 3  
100 4

Example Output  
3 1 2 4

Hint

Author

以下为wrong answer代码——中间插入元素时位置判断条件错误

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    struct node
    {
        int Data;
        struct node *next;
    }*head, *tail;
    
    void Build(int n);
    void Pri(struct node *h);
    
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            head = (struct node *)malloc(sizeof(struct node));
            head->next = NULL;
            tail = head;
            Build(n);
            Pri(head);
        }
        return 0;
    }
    
    void Pri(struct node *h)
    {
        struct node *p;
        p = h->next;
        while(p != NULL)
        {
            printf("%d%c", p->Data, p->next == NULL? '\n': ' ');
            p = p->next;
        }
    }
    void Build(int n)
    {
        struct node *p, *q;
        int a, b, i, cnt, t;
        cnt = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d %d", &a, &b);
            p = (struct node *)malloc(sizeof(struct node));
            p->Data = b;
            if(a == 0)
            {
                p->next = head->next;
                head->next = p;
                if(tail == head)
                    tail = p;
                cnt++;
            }
            else if(a >= cnt)
            {
                p->next = tail->next;
                tail->next = p;
                tail = p;
                cnt++;
            }
            else
            {
                t = 0;
                q = head->next;
                while(q != NULL)
                {
                    t++;
                    if(t == cnt)
                    {
                        p->next = q->next;
                        q->next = p;
                        cnt++;
                        break;
                    }
                    else
                        q = q->next;
                }
            }
        }
    }
    
    
    /***************************************************
    User name: 
    Result: Wrong Answer
    Take time: 0ms
    Take Memory: 180KB
    Submit time: 2017-03-28 20:59:32
    ****************************************************/

以下为accepted代码

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    struct node
    {
        int Data;
        struct node *next;
    }*head, *tail;
    
    void Build(int n);
    void Pri(struct node *h);
    
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            head = (struct node *)malloc(sizeof(struct node));
            head->next = NULL;
            tail = head;
            Build(n);
            Pri(head);
        }
        return 0;
    }
    
    void Pri(struct node *h)
    {
        struct node *p;
        p = h->next;
        while(p != NULL)
        {
            printf("%d%c", p->Data, p->next == NULL? '\n': ' ');
            p = p->next;
        }
    }
    void Build(int n)
    {
        struct node *p, *q;
        int a, b, i, cnt, t;
        cnt = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d %d", &a, &b);
            p = (struct node *)malloc(sizeof(struct node));
            p->Data = b;
            if(a == 0)
            {
                p->next = head->next;
                head->next = p;
                if(tail == head)
                    tail = p;
                cnt++;
            }
            else if(a >= cnt)
            {
                p->next = tail->next;
                tail->next = p;
                tail = p;
                cnt++;
            }
            else
            {
                t = 0;
                q = head->next;
                while(q != NULL)
                {
                    t++;
                    if(t == a)
                    {
                        p->next = q->next;
                        q->next = p;
                        cnt++;
                        break;
                    }
                    else
                        q = q->next;
                }
            }
        }
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 180KB
    Submit time: 2017-03-28 21:04:01
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2024/pid/2874