之前有过整理链表等的概念和基本算法。比较重要的是插入，删除，遍历，建表（尾插法，头插法）
回忆链表尾部插入结点：
1 #include <iostream>
2 using namespace std;
3
4 typedef struct Node{
5 int data;//数据域
6 Node *next;//指针域
7 } Node, *List;
8
9 //在单链表的末位添加一个结点
10 void addNode(List *head, int value)
11 {
12 //先动态的创建结点
13 Node *newNode = new Node();
14 newNode->data = value;
15 newNode->next = NULL;
16 //判断表是否为空,head为头指针
17 if (*head == NULL) {
18 *head = newNode;
19 cout << (*head)->data << endl;
20 }
21 else{
22 //不为空表，尾插，先遍历找到尾结点
23 Node *p = *head;
24 //从头到尾遍历单链表
25 while (p->next != NULL) {
26 //p 作为标记，顺次后移
27 p = p->next;
28 }
29 //找到了尾结点，插入新结点
30 p->next = newNode;
31 cout << p->next->data << endl;
32 }
33 }
34
35 int main(void)
36 {
37 List node = NULL;
38 addNode(&node, 10);
39 addNode(&node, 100);
40
41 return 0;
42 }
要区分链表和顺序表（数组）之间的区别，顺序表（比如数组）可以随机存储，时间复杂度是 o（1），链表是离散的，动态的分配的，只能从头到尾遍历，不能随机存储，时间复杂的是 o（n），且注意空表的情况，还有二级指针的使用问题，注意到了这几点，一般没有问题了。
删除链表中第一个寻找到的目标结点
1 //查找到结点的 data 为val的第一个结点，然后删除之
2 void deleteNode(List *head, int value)
3 {
4 //指示指针
5 Node *p = *head;
6 //指向待删除结点的指针
7 Node *del = NULL;
8 //先判断是否空表
9 if (*head == NULL || head == NULL) {
10 cout << "空表" << endl;
11 exit(0);
12 }
13 //然后判断头结点
14 if ((*head)->data == value) {
15 del = *head;
16 *head = (*head)->next;
17 }
18 //遍历寻找,注意遍历结束的标志有两个，没找到，找到
19 while (p->next !=NULL && p->next->data != value) {
20 p = p->next;
21 }
22 //循环遍历结束，判断找到的情况
23 if (p->next != NULL && p->next->data == value) {
24 del = p->next;
25 //删除
26 p->next = p->next->next;
27 }
28 //销毁内存
29 delete del;
30 //消除野指针
31 del = NULL;
32 }
33
34 void traversal(List head)
35 {
36 Node *p = head;
37 if (p == NULL) {
38 cout << "空表" << endl;
39 exit(0);
40 }
41
42 while (p != NULL) {
43 cout << p->data << endl;
44 p = p->next;
45 }
46 }
47
48 int main(void)
49 {
50 List node = NULL;
51 //traversal(node);
52 addNode(&node, 10);
53 addNode(&node, 100);
54 traversal(node);
55 deleteNode(&node, 10);
56 traversal(node);
57
58 return 0;
59 }
10
100
10
100
100
Program ended with exit code: 0
输入一个链表的头结点，逆序遍历打印该链表
链表的结点结构
typedef struct Node{
int data;//数据域
Node *next;//指针域
} Node, *List;
直接的思路：改变链表的方向，从头到尾输出，也就是把链表的结点的指针反转，但是，这样会改变原单链表的结构，如果不可以改变链表的结构，那么这个方法就不可行。
但是不论怎样，肯定是要遍历链表，只不过这里要求是逆序的遍历，也就是第一个找到的结点，让它最后一个输出。联系到了栈这个数据结构，先进后出。在遍历的时候，每查找到一个结点，就把这个结点压栈，遍历结束，出栈，就是逆序了。
依靠c++ STL stack 实现逆序打印单链表
stack不能遍历，所以没有迭代器，必须添加头文件 #include <stack>
1 //依靠栈来实现逆序打印单链表
2 //输入单链表的头结点，实现单链表的逆序打印
3 void traversalReverse(List head)
4 {
5 //使用 c++ STL stack
6 stack<List> nodes;
7 //指示指针
8 Node *p = head;
9 //遍历
10 while (p != NULL) {
11 //入栈
12 nodes.push(p);
13 //指针后移
14 p = p->next;
15 }
16 //遍历完毕，从栈中输出结点
17 //empty（）方法：堆栈为空则返回真
18 while (!nodes.empty()) {
19 //stack 没有迭代器，取出栈顶元素
20 p = nodes.top();
21 cout << p->data << " ";
22 //出栈
23 nodes.pop();
24 }
25 }
26
27 int main(void)
28 {
29 List node = NULL;
30 addNode(&node, 10);
31 addNode(&node, 100);
32 addNode(&node, 101);
33 addNode(&node, 102);
34 addNode(&node, 103);
35 traversalReverse(node);
36
37 return 0;
38 }
10
100
101
102
103
103 102 101 100 10 Program ended with exit code: 0
联系递归，递归在本质上就是一栈结构，还可以使用递归来直接实现逆序打印单链表
在一次递归中，每次访问到一个结点，先打印该结点的后续一个结点，然后打印该结点本身，这样效果就是把链表逆序打印输出。
1 void traversalRecursive(List head)
2 {
3 //先判断链表是否为空
4 if (head != NULL) {
5 //递归结束的条件
6 if (head->next != NULL) {
7 //先打印该结点的后续结点
8 traversalRecursive(head->next);
9 }
10 //然后打印该结点
11 cout << head->data << "\t";
12 }
13 }
14
15 int main(void)
16 {
17 List node = NULL;
18 addNode(&node, 10);
19 addNode(&node, 100);
20 addNode(&node, 101);
21 addNode(&node, 102);
22 addNode(&node, 103);
23 traversalRecursive(node);
24
25 return 0;
26 }
递归的优点：代码简单明了
递归的缺点：如果链表很长，导致递归调用层次很深，有可能导致函数的调用栈溢出，故一般第一个方法，显式的使用栈来实现逆序打印单链表的鲁棒性要好一些。
何为代码的鲁棒性？
鲁棒是Robust的音译，也就是健壮和强壮的意思。它是在异常和危险情况下系统生存的关键。比如说，计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下，能否不死机、不崩溃，就是该软件的鲁棒性。所谓“鲁棒性”，是指控制系统在一定（结构，大小）的参数影响下，维持其它某些性能的特性。
辛苦的劳动，转载请注明出处，谢谢……
http://www.cnblogs.com/kubixuesheng/p/4322189.html