（本文参考《剑指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
