链表的构建事实上也就是不断插入节点的过程。而节点的插入能够分为头插法和尾插法。

头插法就是在头结点后插入该节点，始终把该节点作为第一个节点。尾插法就是在链表的最后一个节点处插入元素，作为最后一个节点。假设想要了解链表的概念和其它链表操作。请參考《数据结构与算法之链表》《C语言实现链表的基本操作》两篇文章。演示样例代码上传至  https://github.com/chenyufeng1991/HeadInsertAndTailInsert 。

//

//  main.c

//  HeadInsertAndTailInsert

//

//  Created by chenyufeng on 16/2/25.

//  Copyright © 2016年 chenyufengweb. All rights reserved.

//

/**

 *  分别使用头插法和尾插法建立单链表

 */

#include <stdio.h>

#include "stdlib.h"

#include "string.h"

typedef int elemType;

//构造节点

typedef struct ListNode{

    int element;

    struct ListNode *next;

}Node;

//初始化链表

void initList(Node *pNode){

    pNode = NULL;

    printf("%s函数运行，头结点初始化完毕\n",__FUNCTION__);

}

//打印链表

void printList(Node *pNode){

    if (pNode == NULL) {

        printf("%s函数运行，链表为空，打印失败\n",__FUNCTION__);

    }else{

        while (pNode != NULL) {

            printf("%d ",pNode->element);

            pNode = pNode->next;

        }

        printf("\n");

    }

}

//头插法

Node *HeadInsert(Node *pNode){

    Node *pInsert;

    pInsert = (Node*)malloc(sizeof(Node));

    if (pInsert == NULL) {

        printf("%s函数运行。内存分配失败，建立链表失败\n",__FUNCTION__);

        return NULL;

    }

    memset(pInsert, 0, sizeof(Node));

    scanf("%d",&(pInsert->element));

    pInsert->next = NULL;

    if (pInsert->element <= 0) {

        printf("%s函数运行。输入数据有误，建立链表失败\n",__FUNCTION__);

        return NULL;

    }

    while (pInsert->element > 0) {

        if (pNode == NULL) {

            pNode = pInsert;

        }else{

            //注意以下语句的顺序，否则可能造成链断裂

            pInsert->next = pNode;

            pNode = pInsert;

        }

        pInsert = (Node*)malloc(sizeof(Node));

        if (pInsert == NULL) {

            printf("%s函数运行，内存分配失败，建立链表失败\n",__FUNCTION__);

            return NULL;

        }

        memset(pInsert, 0, sizeof(Node));

        scanf("%d",&(pInsert->element));

        pInsert->next = NULL;

    }

    printf("%s函数运行。头插法建立链表成功\n",__FUNCTION__);

    return pNode;

}

//尾插法

Node *TailInsert(Node *pNode){

    Node *pInsert; //要插入的节点

    Node *pMove; //遍历链表的节点

    pInsert = (Node*)malloc(sizeof(Node));

    if (pInsert == NULL) {

        printf("%s函数运行，内存分配失败，建立链表失败\n",__FUNCTION__);

        return NULL;

    }

    memset(pInsert, 0, sizeof(Node));

    scanf("%d",&(pInsert->element));

    pInsert->next = NULL;

    if (pInsert->element <= 0) {

        printf("%s函数运行。输入数据有误，建立链表失败\n",__FUNCTION__);

        return NULL;

    }

    pMove = pNode;

    while (pInsert->element > 0) {

        if (pNode == NULL) {

            //注意不要忘了改动pMove指针的指向，初始pMove一定要指向头节点

            pNode = pInsert;

            pMove = pNode;

        }else{

            //遍历找到最后一个节点

            while (pMove->next != NULL) {

                pMove = pMove->next;

            }

            pMove->next = pInsert;

        }

        pInsert = (Node*)malloc(sizeof(Node));

        if (pInsert == NULL) {

            printf("%s函数运行。内存分配失败，建立链表失败\n",__FUNCTION__);

            return NULL;

        }

        memset(pInsert, 0, sizeof(Node));

        scanf("%d",&(pInsert->element));

        pInsert->next = NULL;

    }

    printf("%s函数运行，尾插法建立链表成功\n",__FUNCTION__);

    return pNode;

}

int main(int argc, const char * argv[]) {

    Node *pList;

    initList(pList);

    printList(pList);

    //头插法建立链表

    pList = HeadInsert(pList);

    printList(pList);

    //尾插法建立链表

    pList = TailInsert(pList);

    printList(pList);

    return 0;

}