链表/堆栈（【常用方式】头节点不存放数据的方式）（C语言版）

常用的链表/堆栈都是先生成一个头指针head 再用头指针申请一个头节点空间，然后头节点的Data 一般是不储存数据的，

{ 当用 malloc函数分配内存后head就变为了名叫head的节点了。而不在是一个单独的指针了 }

{ 注意只要用malloc申请的空间才能使指针再下次循环指向不同的内存空间，即每次申请的内存地址都是一定不相同的，除非free了这个内存空间，否则不可能再次被使用 }

当为链表/堆栈为空时则头节点 head->Next=NULL;否则则指向会储存数据的普通节点；（这样实现的链表/堆栈的空类型判断打印操作都比较方便）

【带头节点（不存放普通数据得）的引入是为了对链表删除、逆向、建立的时候操作更统一，不用专门对第一个元素单独处理。】
3、大部分程序用带头节点来存储链表的长度。
4、如何区分，很简单，看看程序的定义，和程序在建立链表的时候有没针对第一个节点做特殊处理。（做了特殊处理的，则说明头节点储存了数据/即没有头节点 ，只要头指针）

链表（先入先出）

//说明的更加详细的博文-> https://blog.csdn.net/endeavor_g/article/details/80552680 
#include<stdio.h>
#include <stdlib.h> 
/*链表*/
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;//List是一个 struct Node 指针 



List Merge( List L1, List L2 );
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

int main(){
    List  L1,L2,L;
    L1 =  Read();
    L2 = Read();
//    Print(L1);
//    Print(L2);
    L=Merge( L1, L2 );
    printf("
------
");
    Print(L);
    Print(L1);
    Print(L2);
}
List Read() {
    List r,L=(struct Node*)malloc(sizeof(struct Node));//这个空头节点的创建相当于创建了 链表对象；
    L->Next=NULL;//创建一个头节点；一般链表都是带头节点的;头节点的 Data是没有存放数据的 ；当然也可以创建没有头节点的链表；
    //因为带有头节点的 链表，可以让print操作更加简练；因此链表都是有一个 不存放数据的头节点的； 【链表】
    r=L;
    int n;
    scanf("%d",&n);
    while(n--) {///尾插法
        Node *p=(struct Node*)malloc(sizeof(struct Node));
        scanf("%d",&p->Data);
        p->Next=NULL;
        r->Next=p;
        r=p;
    }
    return L;
}
void Print(List L) {
    if(L->Next) {
        List r=L;
        while(r->Next) {
            r=r->Next;
            printf("%d ",r->Data);
        }
        puts("");
    } else {
        printf("NULL
");
    }
}
List Merge(List L1,List L2){
    List p1,p2,p3,head;
    head=(struct Node*)malloc(sizeof(struct Node));
    p3=head;
    p3->Next=NULL;
    p1=L1->Next,p2=L2->Next;
    while(p1&&p2){
        if(p1->Data<=p2->Data){
            p3->Next=p1;
            p3=p3->Next;
            p1=p1->Next;
        }else{
            p3->Next=p2;
            p3=p3->Next;
            p2=p2->Next;
        }
    }
    p3->Next=p1?p1:p2;
    L1->Next=NULL;
    L2->Next=NULL;
    return head;
}

堆栈（后入先出）

#include<stdio.h>
#include<stdlib.h>
typedef struct _node{
    int value;
    struct _node *next;
} Node;

int main(){
    int n=5,number;
    Node *head=(Node*)malloc(sizeof(Node));//创建了一个尾部（空）节点，用于创建堆栈对象；
    Node *end,*node;
    head->next=NULL;
    end=head;
    end->next=NULL;
    while(n--){
        scanf("%1d",&number);
        node=(Node*)malloc(sizeof(Node));
        node->value=number;
//        end->next=node;
//        end=node;
        node->next=head->next;
        head->next=node;
        
    }
    end=node;
//    printf("%d ",end->value);
    while(end){
        printf("%d ",end->value);//这个尾部有一个（空）节点的堆栈与
        end=end->next;//头部有一个（空））节点的 end=end->next的顺序不同 链表是先 end=end->next  
    }
}