链表面试题(一)：逆序打印链表、无头链表删除插入节点、约瑟夫环、逆置单链表

小咪咪 2022-06-13 01:28 202阅读 0赞

这次主要介绍单链表相关的算法题型，这些题在笔试面试中考中频率也是相当高的 可以适当多多练习

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

1）顺序表支持随机访问，单链表不支持随机访问。

2）顺序表插入/删除数据效率很低，时间复杂度为O(N)（除尾插尾删），单链表插入/删除效率更高，时间复杂度为O(1)。

3）顺序表的CPU高速缓存效率更高，单链表CPU高速缓存效率低。

2. 从尾到头打印单链表

//2.从尾到头打印单链表
    void ReversePrintLinkList(pNode pHead)
    {
    	assert(NULL != pHead);
    
    	while (pHead->next != NULL)
    	{
    		ReversePrintLinkList(pHead->next);
    		printf("%d -> ", pHead->_data);
    		return;
    	}
    	printf("%d -> ", pHead->_data);
    
    }

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

//3. 删除一个无头单链表的非尾节点（不能遍历链表）
    void EraseNotTail(pNode pos)
    {
    	pNode del = pos->next;
    	pos->_data = del->_data;
    	pos->next = del->next;
    	free(del);
    
    }

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

//4. 在无头单链表的一个非头节点前插入一个节点
    void InsertFrontNode(pNode* pos, DataType data)
    {
    	assert(NULL != pos);
    	pNode pNewNode = BuyNode(data);
    	pNode pCur = *pos;
    	pNewNode->next = pCur->next;
    	pCur->next = pNewNode;
    	DataType tmp = pCur->_data;
    	pCur->_data = pNewNode->_data;
    	pNewNode->_data = tmp;
    
    }

5. 单链表实现约瑟夫环(JosephCircle)

//5.单链表的约瑟夫环，循环删除第K个节点
    //约瑟夫环（约瑟夫问题）是⼀个数学的应⽤问题：
    // 已知n个⼈（以编号1， 2， 3...n分别表⽰）围坐在⼀张//圆桌周围。
    // 从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈又从1开始报数，数到m的那个⼈
    // 又出列；依此规律重复下去，直到圆桌周围的⼈全部出列。
    pNode JosephCycle(pNode* pHead, int num)//函数执行的前提条件是链表先构成环
    {
    	assert(pHead);
    	pNode pCur = *pHead;
    	int _num = num;
    	while (pCur)
    	{
    		//当只有一个节点时，退出
    		if (pCur == pCur->next)
    			break;
    
    		while (--_num)
    		{
    			pCur = pCur->next;
    		}
    		pNode del = pCur->next;
    		printf("删除 ：%d \n", pCur->_data);
    		pCur->_data = del->_data;
    		pCur->next = del->next;
    		free(del);
    		_num = num;
    	}
    	*pHead = pCur;
    	return pCur;
    }

6. 逆置/反转单链表

//6.逆置单链表
    //以头插方式建立新连接，从而逆置
    void ReverseLinkList(pNode* pHead)
    {
    	pNode pCur = *pHead;
    	pNode prev = pCur;
    	pNode pNewNode = NULL;
    	while (pCur != NULL)
    	{
    		pCur = pCur->next;
    		prev->next = pNewNode;
    		pNewNode = prev;
    		prev = pCur;
    	}
    	*pHead = pNewNode;
    }