Overview
###基础知识
链表是一种很常见的数据结构，在每个节点都保存了指向下一个节点的指针。与顺序表相比，链表插入元素的复杂度是O(1)，查找一个节点或者访问特定节点编号的元素的复杂度是O(n)；顺序表插入元素的复杂度是O(n)，而查找的复杂度是O(1)。使用链表可以不必事先知道数据的大小，但是增加了指针域，加大了内存的开销。链表有三种类型：单向链表、双向链表和循环链表。
###链表节点的定义
1
2
3
4
5
typedef struct linkedNode
{
int value;
struct linkedNode* next;
}node,*pNode;
###链表相关的基本操作（创建和遍历）
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
/*
创建链表
*/
pNode create(int* a,int n)
{
int i;
pNode pHead = (pNode) malloc(sizeof(node));
if(pHead == NULL)
{
exit(0);
}
pNode pTail = pHead;
pTail->next = NULL;
for(i = 0;i < n;i++)
{
pNode nNode = (pNode) malloc(sizeof(node));
if(nNode == NULL)
{
exit(0);
}
nNode->value = a[i];
pTail->next = nNode;
nNode->next = NULL;
pTail = nNode;
}
return pHead;
}
/*
遍历链表
*/
void travel(pNode head)
{
pNode tmp = head->next;
while(tmp != NULL)
{
printf("%d ", tmp->value);
tmp = tmp->next;
}
printf("\n");
}
插入数据、删除数据等操作较为简单且在本文中暂时用不着，所以在此不一一赘述了。
###常见面试题分析
接下来，就下面几个问题进行分别讨论
- 链表的倒数第k个节点
- 链表是否存在环
- 链表的中间节点
- 链表的反序
- 链表的排序
- 仅给定一个非尾节点的节点，删除该节点
- 仅给定一个非空节点，在该节点后插入一个节点
####链表的倒数第k个节点
注意：在这里的倒数第k个节点是从1开始计数，如链表节点有{3,5,7,1,4,6}，倒数第3个节点指的就是值为1的节点。
假设链表有n个节点，倒数第k个节点，也即第n - k + 1个节点。仅遍历一次链表的解法是，定义两个指针。第一步，第一个指针从头指针开始遍历到第k - 1个元素，第二个指针不动；第二步，两个指针同时移动，当第一个指针移到尾指针时，第二个指针正好指向了倒数第k个节点。
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
/*
找到链表的倒数第k个节点
链表节点{3,5,7,1,4,6}，倒数第3个节点是值为1的节点
*/
pNode findKthToTail(pNode head,int k)
{
if(head == NULL || k <= 0)
{
return NULL;
}
int i,j;
pNode pA = head;
pNode pB = head;
for(i = 0;i < k - 1;i++)
{
if(pA->next != NULL)
{
pA = pA->next;
}
else
return NULL;
}
while(pA->next != NULL)
{
pA = pA->next;
pB = pB->next;
}
return pB;
}
####链表是否存在环
判断一个链表是否存在环，可以定义两个指针，一个每次移动一步，另一个每次移动两步。如果每次移动两步的指针指向了NULL，则说明不存在环；如果两个指针相遇，则说明存在环。
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
/*
判断链表是否存在环
*/
bool isExitCycle(pNode head)
{
if(head == NULL)
{
return false;
}
pNode pA = head;
pNode pB = head;
while(pB->next != NULL && pB != NULL)
{
pB = pB->next->next;
pA = pA->next;
if(pA == pB)
{ // 若两个指针相遇，则存在环
return true;
}
}
return false;
}
####链表的中间节点
与判断上一个问题链表是否存在环的问题类似，我们可以定义两个指针，一个每次移动一步，另一个每次移动两步。当每次移动两步的指针指向了链表的尾节点时，每次移动一步的指针正好处于中间位置，即我们要找的中间节点位置。当然，这是在不知道链表的长度，且为了减少时间复杂度的解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
求链表的中间节点
*/
pNode getCenterPoint(pNode head)
{
if (head == NULL || head->next == NULL) //如果链表为空，或仅有头节点
{
return head;
}
pNode pA = head;
pNode pB = head;
while(pB != NULL && pB->next != NULL)
{
pA = pA->next;
pB = pB->next->next;
}
return pA;
}
####链表的反序
求一个链表的反序，需要注意的是不能让链表断开，为此需要三个节点，分别用来保存现节点，节点的前向元素，节点的后向元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
反转链表
*/
pNode reverse(pNode head)
{
pNode rHead = NULL;
pNode mNode = head;
pNode mPre = NULL;
while(mNode != NULL)
{
pNode mNext = mNode->next;
if(mNext == NULL) //当位于原链表尾节点时，将最后一个节点设为新链表的头节点
{
rHead = mNode;
}
mNode->next = mPre;
mPre = mNode;
mNode = mNext;
}
return rHead;
}
####链表的排序
对链表进行排序可以采用冒泡、选择、插入等多种方法，这里采用选择排序来对链表进行排序。具体其他排序方法的思想，可以参考这里。
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
/*
链表的选择排序
*/
void select_sortLink(pNode head)
{
pNode p,q,min;
int tmp;
p = head->next;
while(p->next != NULL)
{
min = p;
q = p->next;
while(q->next != NULL)
{
if(q->value < min->value)
{
min = q;
}
q = q->next;
}
if(min != p)
{
tmp = p->value;
p->value = min->value;
min->value = tmp;
}
p = p->next;
}
}
####仅给定一个非尾节点的节点，删除该节点
在不知道头指针的情况下，要删除一个特定的节点，难以获取该节点的前一个节点，所以将该节点的值设置为下一个节点的值，然后将下一个节点删除即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
在不知链表头指针的情况下，删除节点p。将节点p的下一个节点的值赋给p，然后删除p
*/
void deletePoint(pNode mNode)
{
if(mNode == NULL)
{
return;
}
pNode tmp = mNode->next;
if(tmp == NULL)
{
mNode = NULL;
}
else
{
mNode->value = tmp->value;
mNode->next = tmp->next;
delete tmp;
}
}
####仅给定一个非空节点，在该节点前插入一个节点
与上一题类似，将新的节点插在该节点后，然后将新的节点的值与该节点的值交换即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
将节点q插在节点p前
*/
void insertToPre(pNode p,pNode q)
{
if(p == NULL || q == NULL)
{
return;
}
q->next = p->next;
p->next = q;
int tmp = q->value;
q->value = p->value;
p->value = tmp;
}