（本文参考《剑指offer》总结笔记，供学习使用）
链表是一种动态数据结构，是因为在创建链表的时候，无须知道链表的长度。当插入一个结点时，我们只需要为新结点分配内存，然后调整指针的指向来确保新节点被链接到链表当中。由于没有闲置的内存，链表的空间效率比数组高。
单向链表的结点定义为：
|
1
2
3
4
5
|
struct ListNode
{ int m_nValue;
ListNode* m_pNext;
}; |
例：向链表中插入数据
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include<stdio.h>struct ListNode
{ int m_nValue;
ListNode* m_pNext;
};void createListNode(ListNode** pHead,int n);
void addToTail(ListNode** pHead, int value);
void printList(ListNode** pHead);
void main(){
//建立头结点
ListNode* pHead=new ListNode();
//创建链表，需要指定创建几个结点
createListNode(&pHead,5);//这里需要注意的是，传递的头结点是一个指针的地址。在createListNode函数中传递了pHead，当我们向一个空链表中插入一个结点的时候，新插入的结点就是链表的头指针。由于此时会改动头指针，因此必须把pHead参数设为指向指针的指针，否则出了传递参数的函数pHead仍然是一个空指针
//往链表的结尾添加一个结点
printf("向链表中插入结点：10\n");
addToTail(&pHead,10);
printf("输出链表为：\n");
printList(&pHead);
}void addToTail(ListNode** pHead, int value)
{ ListNode* pNew=new ListNode();
pNew->m_nValue=value;
pNew->m_pNext=NULL;
if(*pHead==NULL)
*pHead=pNew;
else
{
ListNode* pNode=*pHead;
while(pNode->m_pNext!=NULL)
pNode=pNode->m_pNext;
pNode->m_pNext=pNew;
}
}void createListNode(ListNode** pHead,int n){
//这里需要注意的是，传递的头结点是一个指针的地址。在createListNode函数中传递了pHead，当我们向一个空链表中插入一个结点的时候，新插入的结点就是链表的头指针。由于此时会改动头指针，因此必须把pHead参数设为指向指针的指针，否则出了传递参数的函数pHead仍然是一个空指针
int x=0;
ListNode* pNode=*pHead;
printf("please input first ListNode number:");
scanf("%d",&pNode->m_nValue);
pNode->m_pNext=NULL;
for(int i=1;i<n;i++){
printf("please input %d number:",i+1);
ListNode* pNew=new ListNode();
scanf("%d",&x);
pNew->m_nValue=x;
pNew->m_pNext=pNode->m_pNext;
pNode->m_pNext=pNew;
}
}void printList(ListNode** pHead){
ListNode* pNode=*pHead;
while(pNode->m_pNext!=NULL){
printf("%d->",pNode->m_nValue);
pNode=pNode->m_pNext;
}
printf("%d\n",pNode->m_nValue);
} |
例：往链表的结尾添加一个结点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void AddToTail(ListNode** pHead, int value)
｛ //pHead是一个指向指针的指针。因为当我们往一个空链表中插入一个结点时，新插入的结点是链表
//的头指针。由于此时会改动头指针，因此必须把pHead参数设为指向指针的指针，否则出了这个函数
//pHead仍然是一个空指针。
ListNode* pNew=new ListNode();
pNew->m_nValue=value;
pNew->m_pNext=NULL;
if(*pHead==NULL)
*pHead=pNew;
else
{
ListNode* pNode=*pHead;
while(pNode->m_pNext!=NULL)
pNode=pNode->m_pNext;
pNode->m_pNext=pNew;
}
｝ |
注：由于链表中的内存不是一次性分配的，因此我们无法保证链表和数组一样是连续的。
例：从尾到头打印链表
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
//使用栈结构打印链表void PrintListReversingly_Iteratively(ListNode* pHead)
{ std::stack<ListNode*> nodes;
ListNode* pNode = pHead;
while(pNode != NULL)
{
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while(!nodes.empty())
{
pNode = nodes.top();
printf("%d\t", pNode->m_nValue);
nodes.pop();
}
}//使用递归打印链表void PrintListReversingly_Recursively(ListNode* pHead)
{ if(pHead != NULL)
{
if (pHead->m_pNext != NULL)
{
PrintListReversingly_Recursively(pHead->m_pNext);
}
printf("%d\t", pHead->m_nValue);
}
} |
注：基于递归代码简洁，但是当链表非常长的时候，就会导致函数调用层级很深，从而有可能导致函数调用栈溢出。显示用栈基于循环实现的代码鲁棒性更好。
本文转自 叫我北北 51CTO博客，原文链接:http://blog.51cto.com/qinbin/1919695