Liping Zou bio photo

Liping Zou

An Android Developer

Email Twitter Instagram Github

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");
}

插入数据、删除数据等操作较为简单且在本文中暂时用不着,所以在此不一一赘述了。

###常见面试题分析

接下来,就下面几个问题进行分别讨论

  1. 链表的倒数第k个节点
  2. 链表是否存在环
  3. 链表的中间节点
  4. 链表的反序
  5. 链表的排序
  6. 仅给定一个非尾节点的节点,删除该节点
  7. 仅给定一个非空节点,在该节点后插入一个节点

####链表的倒数第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;
}