【数据结构·考研】链表的头插法和尾插法

我们经常考察到的链表形式有“带头结点的链表”和“不带头结点的链表”，因为带头结点的链表能够使我们不必去判断插入的是否是第一个节点，所以是最常见的考法。在做算法题时也一定要注意题目要求的是处理二者中的哪一个。

我们这里介绍的是通过头插法和尾插法来创建带头结点的链表：

/*
结构声明
*/
typedef struct node{
	int val;
	struct node* next;
}ListNode,*LinkList; 
/*
头插法
*/ 
LinkList& createListF(int finish){ //约定以finish结束 
	ListNode* L = new ListNode; //创建新结点 
	L->next = NULL;
	int x;
	cin >> x;
	while(x != finish){
		ListNode* p = new ListNode;
		p->val = x;
		p->next = L->next;
		L->next = p;
		cin>>x;
	} 
	return L;
}
/*
尾插法
*/ 
LinkList& createListR(int finish){ //约定以finish结束
	ListNode* L = new ListNode; //创建新结点 
	ListNode* rear = L; //rear指向表尾 
	int x;
	cin >> x;
	while(x != finish){
		ListNode* p = new ListNode;
		p->val = x;
		rear->next = p; //新结点加到表尾 
		rear = p;
		cin >> x;
	}
	rear->next = NULL;
	return L;
}

尾插法的递归版：

/*
尾插法
*/ 
ListNode* createListR2(int finish){ //约定以finish结束 
	int x;
	cin >> x;
	if(x == finish) return NULL; //递归边界 
	ListNode* p = new ListNode;
	p->val = x;
	p->next = createListR2(finish); //把剩余的创建任务交给下一层 
	return p;	
}

全部代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef struct node{
	int val;
	struct node* next;
}ListNode,*LinkList; 
//头插法 
LinkList& createListF(int finish){ //约定以finish结束 
	ListNode* L = new ListNode; //创建新结点 
	L->next = NULL;
	int x;
	cin >> x;
	while(x != finish){
		ListNode* p = new ListNode;
		p->val = x;
		p->next = L->next;
		L->next = p;
		cin>>x;
	} 
	return L;
}
//尾插法 
LinkList& createListR(int finish){ //约定以finish结束
	ListNode* L = new ListNode; //创建新结点 
	ListNode* rear = L; //rear指向表尾 
	int x;
	cin >> x;
	while(x != finish){
		ListNode* p = new ListNode;
		p->val = x;
		rear->next = p; //新结点加到表尾 
		rear = p;
		cin >> x;
	}
	rear->next = NULL;
	return L;
}
//尾插法 
ListNode* createListR2(int finish){ //约定以finish结束 
	int x;
	cin >> x;
	if(x == finish) return NULL; //递归边界 
	ListNode* p = new ListNode;
	p->val = x;
	p->next = createListR2(finish); //把剩余的创建任务交给下一层 
	return p;	
}
void printList(LinkList& L){
	ListNode* p = L;
	while(p != NULL){
		cout<<p->val<<"->";
		p = p->next;
	}
	cout<<"null";
}
int main(){
	cout<<"迭代头插法创建链表："<<endl; 
	ListNode* q = createListF(9999);
	printList(q->next);
	cout<<endl;
	cout<<"迭代尾插法创建链表："<<endl; 
	ListNode* p = createListR(9999);
	printList(p->next);
	cout<<endl; 
	cout<<"递归尾插法创建链表："<<endl; 
	ListNode* k = new ListNode; 
	k->next = createListR2(9999);
	printList(k->next);
}

代码运行结果：