3n+1数列问题-蒲公英云

3n+1数列问题

Problem Description
有一天小标遇到了经典的3n+1数链问题，他想知道3n+1数链的前k个数是多少。
下面小标来给你介绍一下3n+1数链是什么，
给定一个数n，如果n为偶数，那么下一个数n1 = n / 2;否则n1 = 3 * n + 1;
如果n1为偶数，那么下一个数n2 = n1 / 2;否则n2 = 3 * n1 + 1;
如果n2为偶数，那么下一个数n3 = n2 / 2;否则n3 = 3 * n2 + 1;
…..
小标最近刚刚学习了链表，他想把这两个知识结合一下，所以，他想按照下面的规定去做。
①起始n为10，k为5，链表为空
②判断n为偶数，他会往链表头部加一个5（即n/2），此时链表中序列为5，n变为5 -> NULL
③接下来n==5，判断n为奇数，他会往链表尾部加一个16(即3*n+1),此时链表中序列为5 -> 16 -> NULL
④接下来n==16，判断n为偶数，他会往链表头部加一个8(即n/2),此时链表中序列为8 -> 5 -> 16 -> NULL
⑤接下来n==8，判断n为偶数，他会往链表头部加一个4(即n/2),此时链表中序列为4 - > 8 - > 5 -> 16 -> NULL
⑥接下来n==4，判断n为偶数，他会往链表头部加一个2(即n/2),此时链表中序列为2 - > 4 - > 8 - > 5 -> 16 -> NULL
到此时，小标得到了前k个数，那么输出这个序列。
Ps: 为了变得更容易理解，简单来说就是n为偶数，加在链表头部，n为奇数，加在链表尾部

Input
多组输入。
对于每组数据，每行两个整数1 <= n , k <= 1000，含义如上

Output
输出链表序列

Sample Input
10 5
Sample Output
2 4 8 5 16

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
struct  node *creat (int n,int k)
{
     struct node *head ,*p ,*q;
     head=(struct node *)malloc(sizeof(struct node));
     head->next=NULL;
     while(k)
     {
         if(n%2!=0)
         {
            p=(struct node *)malloc(sizeof(struct node));
            n=n*3+1;
            if(head->next)
            {
                q=head->next;
            }
            else
                q=head;
            while(q->next)
            {
                q=q->next;
            }
            p->data=n;
            p->next=NULL;
            q->next=p;
            q=p;
         }
         else
         {
             p=(struct node *)malloc(sizeof(struct node));
             n=n/2;
             p->data=n;
             p->next =head->next;
             head->next=p;
         }
         k--;
     }
     return head;
}
void print(struct node *head)
 {
     struct node *p;
     p=head->next;
     while(p!=NULL)
     {
         printf("%d",p->data);
         if(p->next!=NULL)
         {
             printf(" ");
         }
         else
         {
             printf("\n");
         }
         p=p->next;
     }
 }
int main()
{
    int n,k;
    struct node *head;
    while(~scanf("%d %d",&n,&k))
    {
        head=creat(n,k);
        print(head);
    }
    return 0;
}

先解释输出函数：为啥外层循环是p!=NULL;里层是p->next !=NULL;外层是让指针一直指向下一个，直到没有。内层最后一项的next 是NULL，也就是不能到达最后一项。
建立函数：先建一个头；如果是奇数，也就是顺序建表，让q指向尾节点，方法是先让他指向头结点或者收个节点，然后一直指向尾部。然后让p插在最后。每次都要找尾节点。

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
struct  node *creat (int n,int k)
{
     struct node *head ,*p ,*tail;
     head=(struct node *)malloc(sizeof(struct node));
     head->next=NULL;
     tail=head;
     while(k)
     {
         if(n%2!=0)
         {
            p=(struct node *)malloc(sizeof(struct node));
            n=n*3+1;
            p->data=n;
            p->next=NULL;
            tail->next=p;
            tail=p;
         }
         else
         {
             p=(struct node *)malloc(sizeof(struct node));
             n=n/2;
             p->data=n;
             p->next =head->next;
             head->next=p;
             while(tail->next!=NULL)
             {
                 tail=tail->next;
             }
         }
         k--;
     }
     return head;
}
void print(struct node *head)
 {
     struct node *p;
     p=head->next;
     while(p!=NULL)
     {
         printf("%d",p->data);
         if(p->next!=NULL)
         {
             printf(" ");
         }
         else
         {
             printf("\n");
         }
         p=p->next;
     }
 }
int main()
{
    int n,k;
    struct node *head;
    while(~scanf("%d %d",&n,&k))
    {
        head=creat(n,k);
        print(head);
    }
    return 0;
}