华科机考:遍历链表

时间限制：1秒空间限制：32768K 

题目描述

建立一个升序链表并遍历输出。

输入描述: 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。

输出描述: 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。

输入例子: 4

             3 5 7 9

输出例子: 3 5 7 9

思路：这与以前直接建立链表不一样，在插入新节点时还需要重新遍历已有的节点，从而来判断插入的位置。具体实现的时候，加个头结点，方便插入操作。（大致过程类似于头插法）

注意：1.行末尾不能有空格

        2.具体进行扫描时，一般来说避免直接对头指针进行操作，while(a&&b)这种结构时，大家要注意a,b的顺序诶（o(╯□╰)o）

代码：

#include <iostream>
#include <algorithm>
using namespace std;
struct node{
   int data;
   node *next;
};
void travel(node *head){//释放掉整个链表,保存指向下一个节点的指针，释放该节点
    node *tmp,*tmp1;
    tmp=head->next;
    delete(head);
    cout<<tmp->data;
    while(tmp->next){
     tmp1=tmp->next;
     delete(tmp);
     cout<<" "<<tmp1->data;
     tmp=tmp1;
    }
    cout<<endl;
}

int main(){
   int n;
   node *head,*p,*temp;
   while(cin>>n){
    head=new node;
    head->data=1;
    head->next=NULL;
    for(int i=0;i<n;i++){
    p=new node;
    cin>>p->data;
    temp=head;
    while(temp->next&&p->data>=temp->next->data){
       temp=temp->next;
    }
    p->next=temp->next;
    temp->next=p;
    }
    travel(head);
   }
}