链表面试题(二)：冒泡排序、合并两个有序链表、查找中间节点、查找倒数K个节点

墨蓝 2022-06-13 01:29 164阅读 0赞

这里接上一篇博客，

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

//7.单链表排序（冒泡排序）
    void BubbleSort(pNode* pHead)
    {
    	assert(NULL != pHead);
    	pNode pCur = *pHead;
    	pNode pPrev = NULL;
    
    	int index1 = 0;
    	int index2 = 0;
    
    	while (pCur != pPrev)
    	{
    		while (pCur->next != pPrev)
    		{
    			if (pCur->_data > pCur->next->_data)
    			{
    				DataType tmp = pCur->_data;
    				pCur->_data = pCur->next->_data;
    				pCur->next->_data = tmp;
    			}
    			pCur = pCur->next;
    		}
    		pPrev = pCur;
    		pCur = *pHead;
    	}
    
    }

8. 合并两个有序链表,合并后依然有序，这里提供非递归和递归两个版本

//8.合并两个有序单链表

//这里是普通版本
    pNode Merge(pNode* pHead1, pNode* pHead2)
    {
    	assert(pHead1&&pHead2);//1.两者均为空
    
    	//2.其中一个为空
    	if (pHead1 != NULL && pHead2 == NULL)
    	{
    		return *pHead1;
    	}
    	else if (pHead1 == NULL && pHead2 != NULL)
    	{
    		return *pHead2;
    	}
    	pNode pCur1 = *pHead1;
    	pNode pCur2 = *pHead2;
    	pNode pNewHead = NULL;
    	//假设为升序合并，判定两个头哪一个作为新链表的头
    	if (pCur1->_data < pCur2->_data)
    	{
    		pNewHead = pCur1;
    		pCur1 = pCur1->next;
    	}
    	else
    	{
    		pNewHead = pCur2;
    		pCur2 = pCur2->next;
    	}
    	pNode prev = pNewHead;
    	while (pCur1&&pCur2)
    	{
    		if (pCur1->_data < pCur2->_data)
    		{
    			prev->next = pCur1;
    			pCur1 = pCur1->next;
    		}
    		else
    		{
    			prev->next = pCur2;
    			pCur2 = pCur2->next;
    		}
    		prev = prev->next;
    	}
    	if (NULL == pCur1)
    	{
    		prev->next = pCur2;
    	}
    	else
    	{
    		prev->next = pCur1;
    	}
    	return pNewHead;
    }

//递归 同样的原理 用递归可以让代码更加简洁
    pNode _Merge(pNode pHead1, pNode pHead2)
    {
    	//一定将pNewHead放前面，容易报错（提示变量未定义）
    	pNode pNewHead = NULL;
    	if (pHead1 == NULL)
    		return pHead1;
    	if (pHead2 == NULL)
    		return pHead2;
    
    	if (pHead1->_data < pHead2->_data)
    	{
    		pNewHead = pHead1;
    		pNewHead->next = _Merge(pHead1->next, pHead2);
    	}
    	else
    	{
    		pNewHead = pHead2;
    		pNewHead->next = _Merge(pHead1, pHead2->next);
    	}
    	return pNewHead;
    }

下面两道题目需要用到查找（Finde()）和获取链表节点个数（GetLinkNode()）的函数

pNode Find(pNode pHead, DataType data)
    {
    	pNode pCur = pHead;
    	while (pCur)
    	{
    		if (pCur->_data == data)
    		{
    			printf("找到了。。。\n");
    			return pCur;
    		}
    		else
    		{
    			pCur = pCur->next;
    		}
    	}
    	printf("没有这个数\n");
    	return NULL;
    }

int GetLinkNode(pNode pHead)
    {
    	pNode pCur = pHead;
    	int number = 0;
    	while (pCur != NULL)
    	{
    		pCur = pCur->next;
    		number++;
    	}
    	return number;
    }

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

//9. 查找单链表的中间节点，要求只能遍历一次链表
    pNode FindMidNode(pNode pHead)
    {
    	pNode pFast = pHead;
    	pNode pSlow = pHead;
    
    	while (pFast && pFast->next)
    	{
    		pFast = pFast->next->next;
    		pSlow = pSlow->next;
    	}
    	return pSlow;
    }

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

//10. 查找单链表的倒数第k个节点，要求只能遍历一次链表
    pNode FindKNode(pNode pHead, int k)
    {
    	pNode pCur = pHead;
    	pNode pPre = pHead;
    	if (GetLinkNode(pHead) < k)
    	{
    		return -1;
    	}
    	while (k--)
    	{
    		pCur = pCur->next;
    	}
    	while (pCur)
    	{
    		pCur = pCur->next;
    		pPre = pPre->next;
    	}
    	return pPre;
    }