单链表常见面试题（基础篇）

1.比较顺序表和链表的优缺点，说说它们分别在什么场景下使用？
2.从尾到头打印单链表
3.删除一个无头单链表的非尾节点
4.在无头单链表的一个节点前插入一个节点
5.单链表实现约瑟夫环
6.逆置/反转单链表
7.单链表排序（冒泡排序&快速排序）
8.合并两个有序链表,合并后依然有序
9.查找单链表的中间节点，要求只能遍历一次链表

10.查找单链表的倒数第k个节点，要求只能遍历一次链表 

1、比较顺序表和链表的优缺点，说说它们分别在什么场景下使用？

给顺序表设定容量的时候，如果每次分配的太小则要不断地申请内存来给它使用，如果太大了则会造成内存浪费。假如当一个顺序表每次增容100个字节，现在顺序表里刚刚存了100个数据，如果要是再想增加一个数据，那么就要再申请100个字节的内存，而现在只需要一个，则剩下的99个字节就会被浪费。

在顺序表里如果要是前插一个数，就要先把后面的数据全部向后移动一位，然后再插入，这样做会大大增加时间复杂度。

但是顺序表在查找起来则比链表方便许多！链表在大量增加数据时比较方便！

2.从尾到头打印单链表 

要将单链表从后向前打印输出有很多种方法，这里我们用常规的方法和递归来写一下

递归

void Printinverse(ListNode *plist)//从尾到头打印链表
{
	ListNode *tmp = plist;
	while(tmp->next != NULL)
	{
		Printinverse(tmp->next);
		break;
	}
	printf("%d->", tmp->data);
}

常规

void test(ListNode *plist)
{
	ListNode *tail = NULL;//创造一个尾节点，当遍历到尾时，让tail想起移位，直到收尾相等
	while(plist != tail)
	{
		ListNode *tmp = plist;
		while(tmp->next != tail)
		{
			tmp = tmp->next;
		}
		tail = tmp;
		printf("%d->", tail->data);
	}
}

3.删除一个无头单链表的非尾节点 

要删除一个

void EraseNonHead(ListNode *pos)//.删除一个无头单链表的非尾节点
{//1->2->3->4->null
	assert(pos);
	ListNode *next = pos->next;
	if(next != NULL)
	{
		pos->next = next->next;
		pos->data = next->data;
	}
	free(next);
	next = NULL;
}

4.在无头单链表的一个节点前插入一个节点 

void InsertNonHead(ListNode *pos, Datatype x)//无头链表插入
{//1->2->3->4->NULL
	assert(pos);
	ListNode *cur = pos->next;
	ListNode *tmp = BuyNode(x);
	pos->next = tmp;
	tmp->next = cur;
	Datatype data = pos->data;
	pos->data = tmp->data;
	tmp->data = data;
}

5.单链表实现约瑟夫环 

先来看看什么是约瑟夫环

void JosephRing(ListNode **pplist, int x, int y, int z)//总共x个人,从第y个开始数，每次数z个人
{
	int i = 0;
	assert(pplist);
	ListNode *tmp = NULL;
	for(i=1; i<=x; i++)
	{
		PushBack(pplist, i);
	}
	tmp = Find(*pplist, x);
	tmp->next = *pplist;
	while(--y)
	{
		*pplist = (*pplist)->next;
	}
	while(*pplist != (*pplist)->next)
	{	
		int count = z;
		while(--count)
			*pplist = (*pplist)->next;
		printf("%d ", (*pplist)->data);
		EraseNonHead(*pplist);
	}
	printf("\n");
	printf("%d\n",(*pplist)->data);
}

6.逆置/反转单链表 
逆置一个单链表和从尾到头打印不一样，打印不改变节点的位置，只是将数据反着打印一遍，而逆置就是要改变节点的位置

可以先创建一个空节点，然后从第一个开始每次在单链表上拿一个节点，前插给创建的节点，单链表的头结点往后移，创建的新节点往前移。当单链表为空的时候，也就逆置完了。

ListNode *reverseList(ListNode **pplist)
{//1、当链表为空或者只有一个节点的时候，直接返回 2、多个节点
	if((*pplist == NULL) || ((*pplist)->next == NULL))
	{
		return *pplist;
	}
	else
	{
		ListNode *newlist = NULL;
		ListNode *cur = *pplist;
		while(cur)
		{
			ListNode *tmp = cur;
			cur = cur->next;
			tmp->next = newlist;
			newlist = tmp;
		}
		return newlist;
	}
}

7.单链表排序（冒泡排序&快速排序） 

定义一个头结点和尾节点，冒泡停止条件为首节点的下个节点不为尾节点，每次比较头结点和下一个几点，当头结点大于下一个节点时交换数据，然后头结点向后移位，直到头结点的下个节点为尾节点时，第一次排序完成然后把尾节点向前移动一位。

在冒泡的时候要注意什么时候停下了，每次交换的次数！

ListNode *BubbleList(ListNode *plist)
{/*定义一个头结点和尾节点，冒泡停止条件为首节点的下个节点不为尾节点，每次比较头结点和下一
个几点，当头结点大于下一个节点时交换数据，然后头结点向后移位，直到头结点的下个节点为
尾节点时，第一次排序完成然后把尾节点向前移动一位。*/
	if(plist == NULL || plist->next == NULL)
	{
		return plist;
	}
	ListNode *tail = NULL;
	ListNode *head = plist;
	while(head->next != tail)
	{
		ListNode *tmp = head;
		while(tmp->next != tail)
		{
			ListNode *next = tmp->next;
			if(tmp->data >= next->data)
			{
				Datatype k = tmp->data;
				tmp->data = next->data;
				next->data = k;
			}
			tmp = next;
		}
		tail = tmp;
	}
	return head;
}

8.合并两个有序链表,合并后依然有序 
要合并两个有序的链表就先把两个链表头结点的较小者先拿出来，然后头结点向后移，依次比较他们的头结点，不断地往新链表的后面插，直到有一个为空的时候就把另一个链表连接到新链表后面

ListNode *Merge(ListNode *plist1, ListNode *plist2)//摘节点法，创建新链表
{//链表为空，两个链表中只有一个有数据， 都有数据
	if(plist1 == NULL && plist2 == NULL)//当全为空时返回任意一个
	{
		return plist1;
	}
	if(plist1 == NULL && plist2 != NULL)//一个为空就返回另一个
	{
		return plist2;
	}
	if(plist1 != NULL && plist2 == NULL)
	{
		return plist1;
	}
	else
	{
		ListNode *newlist = NULL;
		ListNode *cur = NULL;
		if(plist1->data >= plist2->data)//先判断两个头结点哪一个大，把小的那个头结点给新链表的头
		{
			cur = plist2;
			plist2 = plist2->next;
		}
		else
		{
			cur = plist1;
			plist1 = plist1->next;
		}
		newlist = cur;//保存新链表的头节点
		while(plist1 != NULL && plist2 != NULL)//当两个链表都不为空时合并
		{
			if(plist1->data <= plist2->data)//把小的节点往新链表的后面串，直到有一个为空
			{
				cur->next = plist1;
				plist1 = plist1->next;
			}
			else
			{
				cur->next = plist2;
				plist2 = plist2->next;
			}
			cur = cur->next;
		}
		if(plist1 == NULL)//当其中一个为空之时，另一个链表直接连到新链表的后面
			cur->next = plist2;
		if(plist2 == NULL)
			cur->next = plist1;
		return newlist;
	}
}

9.查找单链表的中间节点，要求只能遍历一次链表 
如果有两个人，一个人走路一次走一步，另一个一次走两步，则走两步的人走过的步数一定时走一步人步数的两倍。那么就利用这个原理定义两个节点，一个快节点一次走两步，慢节点一次走一步，当快节点走完后，慢节点就是所要求的中间节点，但是要考虑当链表的节点个数为奇数和偶数的时候。

ListNode *SearchmidNode(ListNode *plist)
{
	assert(plist);
	ListNode *slow = plist;
	ListNode *fast = plist;
	while(fast->next)
	{
		if(fast->next->next == NULL)//如果为偶数个，在快指针的下下步为空的时候只让慢的走一步就返回
		{
			slow = slow->next;
			break;
		}
		slow = slow->next;
		fast = (fast->next)->next;
	}
	return slow;
}

10.查找单链表的倒数第k个节点，要求只能遍历一次链表 

求倒数第k个节点时，和上面的问题分析一样，当慢指针和快指针在没有走之前就让两个相距K的距离，然后再一起走，当快节点走到最后一个时，慢节点的位置恰好就是倒数第K个节点

ListNode *LastKNode(ListNode *plist, Datatype k)
{
	assert(plist);
	ListNode *slow = plist;
	ListNode *fast = plist;
	while(--k)
		fast = fast->next;
	while(fast->next)
	{
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}