Fork me on GitHub

链表面试题

发表于 | 更新于: | 分类于 | | 浏览 次
字数统计: 2,029 | 阅读时长 ≈ 10

关于链表已经学了有一段时间了，今天抽空进行了整理，列出来常见的有关链表的面试题，以下想法如有瑕疵望批评指出，希望能给初学者带来一点参考和价值

从尾到头打印单链表

递归打印

1
2
3
4
5
6
7
8
9
10
11
// 1、从尾到头打印单链表 递归
void ListReversePrint(ListNode *Node)
{
	if (Node == NULL)
	{
		return;
	}

	ListReversePrint(Node->next);
	printf("%d-->",Node->data);
}

非递归打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ListReveresePrint2(ListNode *Node)
{
	ListNode *end = NULL;
	while (end != Node)
	{
		ListNode *cur = Node;
		while (cur->next != end)
		{
			cur = cur->next;
		}
		printf("%d-->",cur->data);
		end = cur;
	}
}

删除一个无头单链表的非尾结点（不能遍历链表）

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//2. 删除一个无头单链表的非尾结点（不能遍历链表）
void ListDelNotFirst(ListNode **Node ,ListNode *pos)
{
	ListNode *del;
	if (Node == NULL)
	{
		return;
	}
	//	pos 位置为第一个结点时，修改指针
	if (pos == *Node)
	{
		*Node = pos->next;
		free(pos);
	}
	// pos 位置不是第一个结点时也不是最后一个结点时
	pos->data = pos->next->data;   //先修改data的值
	del = pos->next;     //将pos->next作为要删除的结点
	pos->next = del->next;
	free(del);
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void TestListDelNotFirst()
{
	ListNode *list = NULL;

	ListPushBack(&list,1);
	ListPushBack(&list,2);
	ListPushBack(&list,3);	
	ListPushBack(&list,4);
	ListPushBack(&list,5);	
	ListPushBack(&list,6);

	ListPrint(list);

	ListDelNotFirst(list,list);

	ListPrint(list);
}

在无头单链表的一个结点前插入一个结点（不能遍历链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//3.在无头单链表的一个结点前插入一个结点（不能遍历链表）

void ListInsertBefore(ListNode **Node ,ListNode *pos ,DataType data)
{
	ListNode *newNode;
	if (*Node == NULL && pos == NULL)
	{
		return;
	}
	//插入的结点是在第一个结点上
	if (pos == *Node)
	{
		ListNode *newNode = CreateNode(data);
		newNode->next = *Node;
		*Node = newNode;
		return;
	}
	//插入的结点不是第一个结点时
	newNode = CreateNode(pos->data);
	newNode->next = pos->next;  //后插
	pos->next = newNode;
	pos->data = data;
}

逆置/反转单链表

思路一：

从第二个结点开始，将其删除，人挪活插在第一个结点处，直到链表结束

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
void listReverse(ListNode **Node)
{
	if (Node == NULL)
	{
		return ;
	}
	if (*Node == NULL)
	{
		return;
	}
	//只有一个结点
	if ((*Node)->next == NULL)
	{
		return ;
	}
	//至少两个结点
	ListNode *cur = *Node;
	while (cur->next != NULL)
	{
		ListNode *rm = cur->next;
		cur->next = rm->next;
		rm->next = *Node;
		*Node = rm;
	}
}

思路二：

改变每个结点的指针指向从而逆置

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
void listReverseRePoint(ListNode **Node)
{
	if (Node == NULL)
	{
		return;
	}
	if (*Node == NULL)
	{
		return;
	}
	if ((*Node)->next == NULL)
	{
		return;
	}

	ListNode *pre = *Node;
	ListNode *cur = (*Node)->next;
	pre->next = NULL;
	
	while (cur != NULL)
	{
		ListNode *temp = cur->next;
		cur->next = pre;
		pre =cur;
		cur = temp;
	}

	*Node = pre;
}

找出两个链表里相同数据

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
// 5.找出两个链表里相同数据
void ListIntersection(ListNode *list1,ListNode *list2)
{
	ListNode *head1 = list1;
	ListNode *head2 = list2;
	
	DataType data;

	if (head1 ==NULL && head2 == NULL)
	{
		return ;
	}

	while (head1 != NULL && head2 != NULL)
	{
		if (head1->data < head2->data)
		{
			head1 = head1->next;
		}
		 if (head1->data > head2->data)
		{
			head2 = head2->next;
		}
		
		if (head1->data == head2->data)
		{
			printf("%d ",head1->data);
			data = head1->data;

			while (head2 != NULL && data == head2->data  )
			{
				head2 = head2->next;
			}
			while (head1 != NULL && data == head1->data )
			{
				head1 = head1->next;
			}
		}
	}
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void TestListInterstion()
{
	ListNode *list1 = NULL;
	ListNode *list2 = NULL;

	ListPushBack(&list1,1);
	ListPushBack(&list1,1);
	ListPushBack(&list1,3);	
	ListPushBack(&list1,4);

	ListPushBack(&list2,2);
	ListPushBack(&list2,2);
	ListPushBack(&list2,4);	
	ListPushBack(&list2,4);

	ListIntersection(list1,list2);
}

单链表实现约瑟夫环

核心代码

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
//6.单链表实现约瑟夫环
ListNode* ListJosephCircle(ListNode *list,DataType k)
{
	//第一步，变成环
	ListNode *tail = list;
	ListNode *cur = list;
	ListNode *pre = NULL;
	int i =0;
#if 0
	if (list == NULL)
	{
		return NULL;
	}
#endif
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = list;

	 
	//第二步，找到第k个数
	while ( cur->next != cur)
	{	
#if 0
        //1 2 3 4 5 6 7 8 
		while (--k)
		{
		
			pre = cur;  //记录剔除结点的前一个结点
			cur = cur->next;
		}
#endif
		for (i=1;i<k;i++)
		{
			pre = cur;  //记录剔除结点的前一个结点
			cur = cur->next;
		}
		
		pre->next =cur->next;
		printf("淘汰：%d\n",cur->data);
		free(cur);

		cur = pre->next;
	}	
	cur->next = NULL;
	return cur;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void TestListJosephCircle()
{
	ListNode *list1 = NULL;
	ListNode *re;
	ListPushBack(&list1,1);
	ListPushBack(&list1,2);
	ListPushBack(&list1,3);	
	ListPushBack(&list1,4);
	ListPushBack(&list1,5);
	ListPushBack(&list1,6);
	
	ListPrint(list1);
	printf("\n");
	re = ListJosephCircle(list1,3);
	printf("%d\n",re->data);
}

合并两个有序的链表，合并后依然有序

具体代码

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
//7.合并两个有序的链表，合并后依然有序
ListNode *ListMerge(ListNode *list1,ListNode *list2)
{
	ListNode *cur1 = list1;
	ListNode *cur2 = list2;
	ListNode *result = NULL;	//结果链表
	ListNode *tail = NULL;		 //结果链表中的最后一个结点，方便尾插
	ListNode *next = NULL;		//保存遍历过程中的下一个结点
	ListNode *node;

	while (cur1 != NULL && cur2 != NULL)
	{
		if (cur1->data <= cur2->data)
		{
			node = cur1;
		}
		else
		{
			node =cur2;
		}

		next = node->next;
		if (result != NULL)
		{
			tail->next = node;
		}
		else
		{
			result = node;
		}
		node->next = NULL;

		tail = node;
	
		
		if (node == cur1)
		{
			cur1 = next;
		}
		else
		{
			cur2 = next;
		}
	}
	//一个链表空了
	if (cur1 == NULL)
	{
		tail->next =cur2;
	}
	if (cur2 == NULL)
	{
		tail->next =cur1;
	}

	return result;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void TestMerge()
{
	ListNode *list1 = NULL;
	ListNode *list2 = NULL;

	ListNode *result = NULL;

	ListPushBack(&list1,1);
	ListPushBack(&list1,2);
	ListPushBack(&list1,3);	
	ListPushBack(&list1,4);

	ListPushBack(&list2,1);
	ListPushBack(&list2,2);
	ListPushBack(&list2,3);	
	ListPushBack(&list2,4);

	result = ListMerge(list1,list2);
	ListPrint(result);
}

查找单链表的中间结点，要求只能遍历一次链表

思路：定义快慢指针，当快指针走完时，慢指针刚好是在中间位置，好比是两人赛跑，跑的快点人的速度是慢的人的二倍

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//8.查找单链表的中间结点，要求只能遍历一次链表
void ListFindMidNode(ListNode *list)
{	
	ListNode *fast = list;
	ListNode *slow = list;

	while (fast != NULL && fast->next != NULL)
	{
		fast = fast->next;
		if (fast == NULL)
		{
			break;
		}
		fast = fast->next;
		if (fast == NULL)
		{
			break;
		}
		slow = slow->next;
	}

	printf("%d\n",slow->data);
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
void TestFindMid()
{
	ListNode *list = NULL;

	ListPushBack(&list,1);
	ListPushBack(&list,2);
	ListPushBack(&list,3);	
	ListPushBack(&list,4);
	ListPushBack(&list,5);	
	ListPushBack(&list,6);

	ListFindMidNode(list);
}

查找单链表中的倒数第K个结点，要求只能遍历一次链表

思路：定义快慢指针，快指针先走k步，满指针再开始走，快指针走完的时候就是慢指针走到倒数第k个结点处

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//9.查找单链表中的倒数第K个结点，要求只能遍历一次链表

void ListFindTailK(ListNode *list,DataType k)
{
	ListNode *fast = list;
	ListNode *slow = list;

	while (k--)
	{
		fast = fast->next;
	}
	while (fast != NULL)
	{
		fast = fast->next;
		slow = slow->next;
	}

	printf("%d\n",slow->data);
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void TestFindTailK()
{
	ListNode *list = NULL;

	ListPushBack(&list,1);
	ListPushBack(&list,2);
	ListPushBack(&list,3);	
	ListPushBack(&list,4);
	ListPushBack(&list,5);	
	ListPushBack(&list,6);
	
	ListFindTailK(list,3);

}

删除单链表中的倒数第K个结点

思路：同查找倒数第k个结点一样，我们定义快慢指针进行异步，还需要定义一个pre来记录要删除结点的先驱，删除后需要指向被删除的下一个

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//10.删除单链表中的倒数第K个结点

void ListDelTailK(ListNode *list, DataType k)
{
	ListNode *fast = list;
	ListNode *slow = list;
	ListNode *pre = NULL;
	
	while (k--)
	{
		fast = fast->next;
	}

	while (fast != NULL)
	{
		pre = slow;
		fast = fast->next;
		slow = slow->next;
	}
	pre->next = slow->next;

	free(slow);

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void TestDelTailK()
{
	ListNode *list = NULL;

	ListPushBack(&list,1);
	ListPushBack(&list,2);
	ListPushBack(&list,3);	
	ListPushBack(&list,4);
	ListPushBack(&list,5);	
	ListPushBack(&list,6);
	
	ListPrint(list);
	printf("\n删除倒数第%d个结点\n",3);
	ListDelTailK(list,3);

	 ListDelNotFirst(list,list);


	ListPrint(list);
}

本文标题:链表面试题

文章作者:LiuXiaoKun

发布时间:2018年10月05日 - 12:10

最后更新:2018年10月05日 - 13:10

原始链接:https://LiuZiQiao.github.io/2018/10/05/链表面试题/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%