头插法、尾插法建立单链表（含详细注释C++）

//以" & "结尾分别以头插法、尾插法创建单链表
#include <iostream>
#include <cstdlib> //malloc()函数头文件，作用：动态开辟空间。

using namespace std;

typedef  char datatype;  //为char起别名，方便建立链表data数据类型修改。
//此示例代码链表数据类型为char，若建立链表存储data数据类型为int，仅将此处改为 typedef int datatype即可。

typedef struct node{//建立node结构体
    datatype data;
    node *next;
}node;

node *InitList(node *L){//初始化单链表；
    L=new node;
    L->next=NULL;
    return L;
}

node *HeadCreatList(node *L){   //头插法，含头结点
    node *p; int flag=1; datatype x;
    while(flag){
        cin>>x;
        if(x!='&'){
            p=new node;
            p->data=x;
            p->next=L->next;   //头插法关键步骤1
            L->next=p;         //头插法关键步骤2
        }
        else flag=0;
    }
    return L;
}

node *RearCreatList(node *L){   //尾插法，含头结点
    node *p;node *r=L; //指针r存储链表当前的尾结点
    int flag=1;datatype x;
    while(flag){
        cin>>x;
        if(x!='&'){
            p=new node;
            p->data=x;
            p->next=NULL;
            r->next=p;      //尾插法关键步骤1：将新建节点p插入链表当前尾结点r后
            r=p;            //尾插法关键步骤2：由于上一操作将p插入链表尾部，此操作更新链表尾部为p。r一直存储链表当前尾结点
        }
        else flag=0;
    }
    return L;
}
void PrintList(node *L){  //输出单链表
    node *q=L->next;
    while(q!=NULL){
        cout<<q->data<<" ";
        q=q->next;
    }
    cout<<endl;
}

int main(){
    node *L1,*L2;
    L1=InitList(L1);cout<<"头插法输入: ";L1=HeadCreatList(L1);
    L2=InitList(L2);cout<<"尾插法输入: ";L2=RearCreatList(L2);
    cout<<"头插法：";PrintList(L1);
    cout<<"尾插法：";PrintList(L2);
    return 0;
}