单链表的创建方法（头插法、尾插法）

单链表的创建方法

单链表是数据结构中比较基础的结构了。对于单链表的的创建方法，比较容易想到的是头插法。但是当要求输入顺序与链表连接的顺序一致时，那么头插法就不是很友好了。因此了解单链表的尾插法也是很重要。 首先定义了单链表节点的数据结构ListNode，具体代码如下：

struct ListNode { int data; ListNode *next = NULL; };

头插法

头插法，顾名思义就是从单链表的头指针处插入节点，优点是思路简单，比较符合单链表的正常思路，缺点就是插入顺序与链表连接顺序相反。头插法的操作步骤如下：

创建一个节点newNode；保存头指针head.next的副本temp；让头指针指向newNode，newNode.next指向temp; 代码实现： void creatList_front(ListNode* const &h, const int &a) { ListNode *newNode = new ListNode;//步骤一 newNode->data = a;//步骤一 ListNode *temp = h->next;//步骤二 h->next = newNode;//步骤三 newNode->next = temp;//步骤三 }

尾插法

尾插法，就是从尾部插入节点的，优点是插入顺序与链表连接顺序一致。因为头插法有了头指针，所以尾插法要声明一个尾指针tail，它始终指向链表的最后一个节点，因此给定一个单链表时head时，要用尾插法插入节点必须先找到该链表最后一个节点，并让tail指向它，如果链表为空那么，tail = head; 尾插法的操作步骤：

创建尾指针tail，使tial指向链表的最后一个节点；创建新节点newNode;使tail->next指向新节点newNode；让tail指向newNode;

代码实现如下：

void creatList_back(ListNode * &t, const int &a) {//可以在外部先找到tail，再调用该函数 ListNode *newNode = new ListNode;//步骤二 newNode->data = a;//步骤二 t->next = newNode;//步骤三 t = newNode;//步骤四 }

综合两种方法来试一试：

先用头插法插入一部分数据，再用尾插法插入一部分，看看效果如何。

#include<iostream> using namespace std; struct ListNode { int data; ListNode *next = NULL; }; /*头插法*/ void creatList_front(ListNode* const &h, const int &a) { ListNode *newNode = new ListNode;//步骤一 newNode->data = a;//步骤一 ListNode *temp = h->next;//步骤二 h->next = newNode;//步骤三 newNode->next = temp;//步骤三 } /*尾插法*/ void creatList_back(ListNode * &t, const int &a) {//可以在外部先找到tail，再调用该函数 ListNode *newNode = new ListNode;//步骤二 newNode->data = a;//步骤二 t->next = newNode;//步骤三 t = newNode;//步骤四 } int main() { ListNode* head = new ListNode; int a; /*先用头插法插入一部分数据*/ while (cin >> a) creatList_front(head, a); cin.clear(); cin.ignore(); /*再用尾插法插入一部分数据*/ ListNode *tail = head; while (tail->next != NULL)tail = tail->next;//找到尾结点 while (cin >> a)creatList_back(tail, a); /*输出链表*/ ListNode *p = head->next; while (p != NULL) { cout << p->data << ends; p = p->next; } return 0; }

第一次输入：1 2 3 4 (ctrl+Z) 第二次输入：5 6 7 8 (ctrl+Z) 输出：4 3 2 1 5 6 7 8

运行结果：