2020考研-王道数据结构-线性表-链表

布满荆棘的人生 2022-02-03 06:19 298阅读 0赞

# 注意 #

#### 1. 每道题目以函数的形式给出。 ####

#### 2. 为了提高代码的可读性，STL库中的有的函数不在重复，比如Reverse、Swap、Sort等函数。 ####

#### 3. 语言采用的是C++11标准，所以大家编译调试的需要注意，某些函数C++98的编译器不支持。 ####

#### 4. 数据结构、元素定义、相关辅助函数请看以下定义。 ####

typedef int ElemType;
    typedef struct Node
    {
        
    	ElemType data;
    	struct Node *next;
    }LinkList, *PLinkList;
    
    // type == 1 带头节点
    // 计算链表的长度
    int length(PLinkList &la, int type)
    {
        
    	int res = 0;
    	PLinkList tmp = la;
    	while (tmp){
        
    		res++;
    		tmp = tmp->next;
    	}
    	return type ? res - 1 : res;
    }
    
    // type == 0, 不带头节点， type == 1 带头节点
    // 顺次打印链表
    void printLinkList(PLinkList list, int type)
    {
        
    	if (list == NULL) return;
    	PLinkList tmp = list;
    	if (type == 1) tmp = list->next;
    	while (tmp)
    	{
        
    		cout << tmp->data << " ";
    		tmp = tmp->next;
    	}
    	cout << endl;
    	return;
    }
    
    // type == 0, 不带头节点， type == 1 带头节点
    // 创建一个链表
    void createLinkList(PLinkList &list, int type, int len)
    {
        
    	PLinkList tmp = list;
    	// 如果先前传进来的list列表不是空表就释放掉
    	while (list){
         
    		list = list->next;
    		free(tmp);
    		tmp = list;
    	}
    	// 建表
    	list = new LinkList();
    	list->next = NULL;
    	tmp = list;
    	for (int i = 0; i < len; i++)
    	{
        
    		tmp->next = new LinkList();
    		tmp->next->next = NULL;
    		tmp->next->data = rand() % 10;
    		tmp = tmp->next;
    	}
    	if (type == 0)
    	{
        
    		tmp = list;
    		list = list->next;
    		free(tmp);
    	}
    	return;
    }

# 1. 第一题 #

##### 题目简述 #####

删除不带头节点的链表中所有值为x的元素，递归实现。

##### 代码 #####

// P1 删除所有值为x的结点 不带头节点，递归实现
    void delete_x_nohead(PLinkList &list, ElemType x)
    {
        
    	if (list == NULL)
    		return;
    	if (list->data == x)
    	{
        
    		PLinkList tmp = list;
    		list = list->next;
    		free(tmp);
    	}
    	delete_x_nohead(list->next, x);
    }

# 2. 第二题 #

##### 题目简述 #####

删除带头节点的链表中所有值为x的元素。

##### 代码 #####

// P2 删除所有值为x的节点 带头节点
    void delete_x_head(PLinkList &list, ElemType x)
    {
        
    	PLinkList tmp = list;
    	PLinkList del = NULL;
    	while (tmp->next)
    	{
        
    		if (tmp->next->data == x)
    		{
        
    			del = tmp->next;
    			tmp->next = del->next;
    			free(del);
    		}
    		else 
    			tmp = tmp->next;
    	}
    	return;
    }

# 3. 第三题 #

##### 题目简述 #####

反向输出带头节点的链表。

##### 题目思路 #####

很简单的一种递归，和栈的原理一样，需要注意的是，如果是带头节点的链表传参时，应该略过头节点，比如反向输出带头节点的链表list时，应该传入**reversePrintLinkList(list->next)。**

##### 代码 #####

// P3 L带头节点，反向输出链表
    void reversePrintLinkList(PLinkList list)
    {
        
    	if (list == NULL) return;
    	reversePrintLinkList(list->next);
    	cout << list->data << " ";
    	return;
    }

# 4. 第四题 #

##### 题目简述 #####

带头节点的链表中删除最小值的元素。

##### 代码 #####

// p4 带头节点删除最小值元素
    void delete_min(PLinkList &list)
    {
        
    	PLinkList minp = list;
    	PLinkList tmp = list;
    	while (tmp->next)
    	{
        
    		if (tmp->next->data < minp->next->data)
    		{
        
    			minp = tmp;
    		}
    		tmp = tmp->next;
    	}
    	PLinkList delp = minp->next;
    	minp->next = delp->next;
    	free(delp);
    	return;
    }

# 5. 第五题 #

##### 题目简述 #####

将带头节点的单链表倒置，不允许使用额外空间。

##### 代码 #####

// p5 倒置带头节点的链表， 不允许使用额外空间
    void reverseLinkList(PLinkList &list)
    {
        
    	PLinkList cur = list->next, tail = NULL;
    	while (cur)
    	{
        
    		PLinkList p = cur->next;
    		cur->next = tail;
    		tail = cur;
    		cur = p;
    	}
    	list->next = tail;
    	return;
    }

# 6. 第六题 #

##### 题目简述 #####

将带头节点的单链表按升序排序。

##### 题目思路 #####

课本上给出的做法时使用插入排序，那样做的时间复杂度时O(n\*n)，下面这种做法是课本中提到的第二种以空间换时间的一种做法，先放到数组里再利用快排进行排序，最后再放回单链表，这样做的时间复杂度是O(n \* lg(n))。

##### 代码 #####

// p6 头节点的单链表，使其递增有序， 书上的第二种方法 空间换时间 时间复杂度 O(n*lg(n))
    void sort_headLinkList(PLinkList &list)
    {
        
    	vector<ElemType> vec;
    	PLinkList tmp = list;
    	while (tmp->next)
    	{
        
    		vec.push_back(tmp->data);
    		tmp = tmp->next;
    	}
    	sort(vec.begin(), vec.end());
    	tmp = list->next;
    	for (int i = 0; i < vec.size(); i++, tmp = tmp->next) tmp->data = vec[i];
    	return;
    }

# 7. 第七题 #

##### 题目简述 #####

删除带头节点的单链表中，节点的值介于A和B之间的所有节点。

##### 代码 #####

// p7 删除带头节点的链表中的介于A和B之间的值
    void deleteValueInA_B(PLinkList &list, ElemType A, ElemType B)
    {
        
    	PLinkList tmp = list;
    	while (tmp->next)
    	{
        
    		if (tmp->next->data <= B && tmp->next->data >= A)
    		{
        
    			PLinkList del = tmp->next;
    			tmp->next = del->next;
    			free(del);
    		}
    		else
    			tmp = tmp->next;
    	}
    	return;
    }

# 8. 第八题 #

##### 题目简述 #####

找出两个带头节点的单链表中的公共节点，并以表的形式返回。

##### 代码 #####

// p8 找出带头节点两个单链表中的公共节点，并以表lc返回
    void findSameNode(PLinkList la, PLinkList lb, PLinkList &lc)
    {
        
    	lc = new LinkList(); // 清空表lc, 创建一个头节点
    	lc->next = NULL;
    	int lena = length(la, 1), lenb = length(lb, 1);
    	if (lena < lenb){
         
    		swap(la, lb); 
    		swap(lena, lenb);
    	}
    	PLinkList ta = la->next, tb = lb->next;
    	for (int i = 0; i < lena - lenb; i++, ta = ta->next);
    	while (ta && ta != tb){
        
    		ta = ta->next;
    		tb = tb->next;
    	}
    	lc = ta;
    	return;
    }

# 9. 第九题 #

##### 题目简述 #####

升序输出带头节点的单链表，并释放节点。

##### 代码 #####

// p9 升序输出带头节点的单链表。并释放节点
    void printfIncrease(PLinkList la){
        
    	PLinkList il = NULL, jl = NULL;
    	PLinkList minl = la;
    	while (la->next){
        
    		minl = la;
    		il = la;
    		while (il->next){
        
    			if (minl->next->data > il->next->data){
        
    				minl = il;
    			}
    			il = il->next;
    		}
    		cout << minl->next->data << " ";
    		jl = minl->next;
    		minl->next = jl->next;
    		free(jl);
    	}
    	return;
    }

# 10. 第十题 #

##### 题目简述 #####

将带头节点的链表A按照序号为奇数还是偶数，分成两个带头节点的单链表。

##### 代码 #####

// p10 将带头节点的链表按照奇序号和偶序号分为两个带头节点的链表
    void assortWithID1(PLinkList list, PLinkList &la, PLinkList &lb)
    {
        
    	la = new LinkList(); la->next = NULL;
    	lb = new LinkList(); lb->next = NULL; //清空两个将要返回值的链表
    	int cnt = 1; // 节点序号计数器
    	PLinkList tmp = list->next;
    	PLinkList ta = la, tb = lb; // 记录奇偶链表的尾节点
    	// 注意这种方式没有产生新的节点，是将list中的节点分到了la，lb中
    	// 那么，这种方式当while循环结束后，已经改变了list链表
    	while (tmp)
    	{
        
    		if (cnt & 1){
         // 为奇数保存到链表la
    			ta->next = tmp;
    			ta = tmp;
    		}
    		else{
         // 为偶数保存到链表lb
    			tb->next = tmp;
    			tb = tmp;
    		}
    		tmp = tmp->next;
    		cnt++;
    	}
    	ta->next = NULL;
    	tb->next = NULL;
    }

# 11. 第十一题 #

##### 题目简述 #####

将偶数个元素的、带头节点的链表list，按照奇数、偶数拆分成两个链表， la采用头插法，lb采用尾插法。

##### 代码 #####

// p11 将偶数个元素的、带头节点的链表list，按照奇数、偶数拆分成两个链表，
    // la采用头插法，lb采用尾插法
    void assortWithID2(PLinkList list, PLinkList &la, PLinkList &lb)
    {
        
    	la = new LinkList();
    	lb = new LinkList(); // 清空将要返回结果的两个单链表
    	la->next = lb->next = NULL;
    	PLinkList tmp = list->next;
    	PLinkList ta = la; // la是尾插法，所以要记录尾巴的位置
    	// 因为题目中说了一定是偶数个元素，所以一次循环可以更改两个元素
    	while (tmp)
    	{
        
    		ta->next = new LinkList(); // 刚才的p10 说了，那样的做法会改变list 下面这种则不会
    		ta->next->data = tmp->data; // copy
    		ta->next->next = NULL;
    		ta = ta->next;
    		tmp = tmp->next;
    		
    		PLinkList t = new LinkList();
    		t->next = lb->next;
    		t->data = tmp->data;
    		lb->next = t; // 头插法， 最好画图模拟，好理解
    		tmp = tmp->next;
    	}
    	return;
    }

# 12. 第十二题 #

##### 题目简述 #####

带头节点、有序的单链表中，去掉重复元素。

##### 代码 #####

// p12 带头节点、有序的单链表中，去掉重复元素
    void deWeightLinkList(PLinkList &list)
    {
        
    	if (!list->next) return; // 保证链表中至少含有一个元素，否则循环会报错
    	PLinkList tmp = list->next;
    	while (tmp->next)
    	{
        
    		if (tmp->data == tmp->next->data)
    		{
        
    			PLinkList dl = tmp->next;
    			tmp->next = dl->next;
    			free(dl);
    		}
    		else
    			tmp = tmp->next;
    	}
    	return;
    }

# 13. 第十三题 #

##### 题目简述 #####

将两个带头节点的有序的单链表，合并成一个递减的链表，要求不能产生新节点，要用原来链表中的节点。

##### 代码 #####

// p13 将两个带头节点的有序的单链表，合并成一个递减的链表
    // 要求不能产生新节点，要用原来链表中的节点
    void mergeToDecline(PLinkList la, PLinkList lb, PLinkList &lc)
    {
        
    	lc = new LinkList(); lc->next = NULL; // 清空链表
    	PLinkList ta = la->next, tb = lb->next;
    	PLinkList p1 = NULL, p2 = NULL; // 辅助临时节点
    	while (la || lb){
        
    		if (la && lb){
        
    			if (la->data > lb->data) p1 = lb, lb = lb->next;
    			else p1 = la, la = la->next;
    		}
    		else if (la) p1 = la, la = la->next;
    		else p1 = lb, lb = lb->next;
    		p1->next = lc->next;
    		lc->next = p1;
    	}
    	return;
    }

# 14. 第十四题 #

##### 题目简述 #####

要求从la和lb的公共节点中产生表lc，不能破坏表la，lb的节点，其中要求la，lb，lc均为带头节点的单链表。

##### 代码 #####

// p14 要求从la和lb的公共节点中产生表lc，不能破坏表la，lb的节点
    // 都是带头节点的
    void getPublicNodeFromAB(PLinkList la, PLinkList lb, PLinkList &lc)
    {
        
    	lc = new LinkList(); lc->next = NULL; // 清空表lc
    	PLinkList ta = la->next, tb = lb->next, tc = lc;
    	while (ta && tb)
    	{
        
    		if (ta->data == tb->data){
        
    			tc->next = new LinkList();
    			tc->next->data = ta->data;
    			tc->next->next = NULL;
    			tc = tc->next;
    			ta = ta->next;
    			tb = tb->next;
    		}
    		else if (ta->data < tb->data)
    			ta = ta->next;
    		else
    			tb = tb->next;
    	}
    	return;
    }

# 15. 第十五题 #

##### 题目简述 #####

找出链表a和b的交集。

##### 题目思路 #####

这个不难看出和上一题的思路是相同的，所以代码完全参考第十四题即可，如果说不同的地方的话，那就是，14题的代码，并没把其余节点释放空间，而15题需要把非公共节点释放掉。

# 16. 第十六题 #

##### 题目简述 #####

判断表b是不是表a的连续子序列。

##### 代码 #####

// p16 判断lb是否是la的连续子序列 no test
    bool isAIncluedB(PLinkList la, PLinkList lb)
    {
        
    	PLinkList ta = la->next, tb = lb->next;
    	PLinkList pre = la->next;
    	while (tb && ta){
        
    		if (ta->data == tb->data){
        
    			ta = ta->next;
    			tb = tb->next;
    		}
    		else
    		{
        
    			ta = pre->next;
    			tb = lb->next;
    		}
    	}
    	if (tb)
    		return false;
    	return true;
    }

# 17. 第十七题 #

##### 题目简述 #####

判断循环双链表是否对称。

##### 代码 #####

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <ctime>
    
    using namespace std;
    
    typedef int Elemtype;
    
    typedef struct dnode{
        
    	Elemtype data;
    	struct dnode *pre, *next;
    }DNode, *LDNode;
    
    // 创建一个双向循环链表
    void createDNode(LDNode &list, int len)
    {
        
    	list = new DNode();
    	list->pre = list;
    	list->next = list;
    	LDNode tail = list;
    	for (int i = 0; i < len; i++)
    	{
        
    		LDNode tmp = new DNode();
    		tmp->data = rand() % 2;
    		tmp->next = tail->next;
    		tmp->pre = tail;
    		tail->next->pre = tmp;
    		tail->next = tmp;
    		tail = tmp;
    	}
    	return;
    }
    
    void printFrontToBack(LDNode list)
    {
        
    	LDNode tmp = list->next;
    	while (tmp != list)
    	{
        
    		cout << tmp->data << " ";
    		tmp = tmp->next;
    	}
    	cout << endl;
    	return;
    }
    
    void printBackToFront(LDNode list)
    {
        
    	LDNode tmp = list->pre;
    	while (tmp != list)
    	{
        
    		cout << tmp->data << " ";
    		tmp = tmp->pre;
    	}
    	cout << endl;
    	return;
    }
    
    // 是否对称
    bool isSymmetry(LDNode list)
    {
        
    	LDNode l = list->next, r = list->pre;
    	while (l != r && l->next != r)
    	{
        
    		if (l->data != r->data)
    			return false;
    		else
    		{
        
    			l = l->next;
    			r = r->pre;
    		}
    	}
    	if (l->next == r)
    		return l->data == r->data;
    	return true;
    }
    
    int main()
    {
        
    	srand(time(0));
    	LDNode list = NULL;
    	createDNode(list, 4);
    	printFrontToBack(list);
    	printBackToFront(list);
    	if (isSymmetry(list))
    		cout << "对称" << endl;
    	else
    		cout << "不对称" << endl;
    
    	return 0;
    }

# 18.19. 第十八、十九题 #

##### 题目简述 #####

都是循环单链表的题目，所以代码写到了一起。  
18. 把两个循环单链表合并成一个。  
19. 循环输出循环单链表中的最小值节点，并释放掉，直至表空。

##### 代码 #####

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <ctime>
    
    using namespace std;
    
    typedef int Elemtype;
    
    typedef struct node
    {
        
    	Elemtype data;
    	struct node *next;
    }LNode, *PLNode;
    
    // 创建循环单链表
    void createCycleLNode(PLNode &list, int len)
    {
        
    	list = new LNode();
    	list->next = list;
    	PLNode tail = list;
    	for (int i = 0; i < len; i++)
    	{
        
    		PLNode tmp = new LNode();
    		tmp->next = tail->next;
    		tmp->data = rand() % 10;
    		tail->next = tmp;
    		tail = tmp;
    	}
    	return;
    }
    
    // 输出循环单链表
    void printCycleLNode(PLNode list)
    {
        
    	PLNode tmp = list->next;
    	while (tmp != list)
    	{
        
    		cout << tmp->data << " ";
    		tmp = tmp->next;
    	}
    	cout << endl;
    	return;
    }
    
    // p18 把lb加到la上使之循环结构依旧成立
    void addCycleLNode(PLNode &la, PLNode lb)
    {
        
    	if (!lb->next) return; 
    	PLNode taila = la, tailb = lb;
    	while (taila->next != la) taila = taila->next; // 找到a的尾巴
    	while (tailb->next != lb) tailb = tailb->next; // 找到b的尾巴
    	taila->next = lb->next;
    	tailb->next = la;
    }
    
    // p19 找出循环单链表的最小值的节点并删除
    void printMinDel(PLNode &list)
    {
        
    	PLNode pre = list;
    	PLNode tmp = list->next;
    	while (list->next != list)
    	{
        
    		pre = list;
    		PLNode t2 = list;
    		while (t2->next != list){
        
    			if (t2->next->data < pre->next->data) pre = t2;
    			t2 = t2->next;
    		}
    		cout << pre->next->data << " ";
    		PLNode del = pre->next;
    		pre->next = del->next;
    		free(del);
    	}
    	cout << endl;
    }
    
    int main()
    {
        
    	srand(time(0));
    	PLNode list1 = NULL, list2 = NULL;
    	createCycleLNode(list1, 2);
    	createCycleLNode(list2, 5);
    	addCycleLNode(list1, list2);
    	printCycleLNode(list1);
    	printMinDel(list1);
    	return 0;
    }

# 20. 第二十题 #

##### 题目简述 #####

在结构体中加入freq，频率定义。  
定义Locate(list，x)操作，把list中值为x的元素的freq++，并按照元素的freq属性，降序排序。

##### 代码 #####

#include <iostream>
    #include <algorithm>
    #include <ctime>
    
    using namespace std;
    
    typedef int Elemtype;
    
    typedef struct dnode
    {
        
    	Elemtype data;
    	struct dnode *pre, *next;
    	int freq; // 频率
    }DNode, *PDNode;
    
    // 创建一个双向循环链表
    void createDNode(PDNode &list, int len)
    {
        
    	list = new DNode();
    	list->next = list;
    	list->pre = list;
    	PDNode tail = list;
    	for (int i = 0; i < len; i++)
    	{
        
    		PDNode tmp = new DNode();
    		tmp->next = tail->next;
    		tmp->pre = tail;
    		tmp->data = rand() % 10;
    		tmp->freq = 0;
    		tmp->next->pre = tmp;
    		tail->next = tmp;
    		tail = tmp;
    	}
    	return;
    }
    
    // 从前打印双向链表
    void printFrontToBack(PDNode list){
        
    	PDNode tmp = list->next;
    	while (tmp != list)
    	{
        
    		cout << tmp->data << " ";
    		tmp = tmp->next;
    	}
    	cout << endl;
    	return;
    }
    
    // 从后往前打印双向链表
    void printBackToFront(PDNode list)
    {
        
    	PDNode tmp = list->pre;
    	while (tmp != list)
    	{
        
    		cout << tmp->data << " ";
    		tmp = tmp->pre;
    	}
    	cout << endl;
    	return;
    }
    
    void Locate(PDNode &list, Elemtype x)
    {
        
    	PDNode tmp = list->next;
    	while (tmp != list)
    	{
        
    		if (tmp->data == x)
    		{
        
    			tmp->freq++;
    			PDNode p = tmp;
    			while (p->pre != list && p->freq >= p->pre->freq){
        
    				swap(p->data, p->pre->data);
    				swap(p->freq, p->pre->freq);
    				p = p->pre;
    			}
    		}
    		tmp = tmp->next;
    	}
    	return;
    }
    
    int main()
    {
        
    	srand(time(0));
    
    	PDNode list = NULL;
    	createDNode(list, 20);
    
    	printFrontToBack(list);
    
    	while (true)
    	{
        
    		int n; cin >> n;
    		Locate(list, n);
    		printFrontToBack(list);
    	}
    
    	return 0;
    }

# 21. 第二十一题 #

##### 题目简述 #####

查找链表中的倒数第k个元素。

##### 代码 #####

// p21 查找倒数第k个元素
    ElemType findLastK(PLinkList list, int k)
    {
        
    	ElemType res;
    	int cnt = 0;
    	PLinkList tp = list->next;
    	PLinkList rp = tp;
    	while (tp)
    	{
        
    		if (cnt < k)
    		{
        
    			cnt++;
    		}
    		else
    			rp = rp->next;
    		tp = tp->next;
    	}
    	if (cnt == k)
    		return rp->data;
    	cerr << "error!" << endl;
    	return -1;
    }

# 22. 第二十二题 #

##### 题目简述 #####

找到链表中的公共节点，和前面的第八题类似。

##### 代码 #####

#include <iostream>
    #include <algorithm>
    #include <string>
    
    using namespace std;
    
    typedef char Elemtype;
    
    typedef struct node{
        
    	Elemtype data;
    	struct node *next;
    }StrList, *PStrList;
    
    int len(PStrList list){
        
    	int cnt = 0;
    	PStrList tmp = list->next;
    	while (tmp)
    	{
        
    		cnt++;
    		tmp = tmp->next;
    	}
    	return cnt;
    }
    
    // 创造链表字符串
    void createStrList(PStrList &list, string str)
    {
        
    	list = new StrList(); list->next = NULL;
    	PStrList tail = list;
    	for (int i = 0; i < str.size(); i++)
    	{
        
    		PStrList p = new StrList();
    		p->next = tail->next;
    		p->data = str[i];
    		tail->next = p;
    		tail = p;
    	}
    	return;
    }
    
    // 输出链表字符串
    void printStrList(PStrList list)
    {
        
    	PStrList tmp = list->next;
    	while (tmp){
        
    		cout << tmp->data;
    		tmp = tmp->next;
    	}
    	cout << endl;
    	return;
    }
    
    // p22 找到公共节点
    PStrList findPublicNode(PStrList la, PStrList lb)
    {
        
    	PStrList res = NULL;
    	int lena = len(la), lenb = len(lb);
    	if (lena < lenb) {
         swap(la, lb); swap(lena, lenb); }
    	PStrList ta = la, tb = lb;
    	for (int i = 0; i < lena - lenb; i++) ta = ta->next;
    	while (ta->next){
        
    		if (ta->next == tb->next)
    			return ta->next;
    		ta = ta->next;
    		tb = tb->next;
    	}
    
    	return res;
    }
    
    void mergeList(PStrList &la, PStrList &lb)
    {
        
    	int lena = len(la), lenb = len(lb);
    	PStrList ta = la, tb = lb, publicnodea = NULL, publicnodeb = NULL;
    	if (lena > lenb) for (int i = 0; i < lena - lenb; i++) ta = ta->next;
    	if (lenb > lena) for (int i = 0; i < lenb - lena; i++) tb = tb->next;
    	while (ta->next){
        
    		if (ta->next->data != tb->next->data)
    		{
        
    			publicnodea = ta->next;
    			publicnodeb = tb->next;
    		}
    		ta = ta->next;
    		tb = tb->next;
    	}
    	publicnodea->next = publicnodeb->next;
    	return;
    }
    
    int main()
    {
        
    	PStrList list = NULL, list2 = NULL;
    	createStrList(list, "zhuyunpeng");
    	createStrList(list2, "sunrongxiaopeng");
    	mergeList(list, list2);
    	printStrList(list);
    	printStrList(list2);
    
    	PStrList publicnode = findPublicNode(list, list2);
    	if (publicnode == NULL)
    		cout << "未找到！" << endl;
    	else
    		cout << publicnode->data << endl;
    	return 0;
    }

# 23. 第二十三题 #

##### 题目简述 #####

删除链表中的元素的绝对值重复的元素，要求|data| <= n。

##### 代码 #####

// p23 删除重复元素，时间复杂度尽可能小, |data| <= n
    void repeatElemtype(PLinkList &list, int n)
    {
        
    	int *cnt = new int[n + 1];
    	memset(cnt, 0, sizeof(int) * (n + 1));
    	PLinkList tmp = list;
    	while (tmp->next)
    	{
        
    		int t = abs(tmp->next->data);
    		if (!cnt[t]) cnt[t]++, tmp = tmp->next;
    		else{
        
    			PLinkList del = tmp->next;
    			tmp->next = del->next;
    			free(del);
    		}
    	}
    }