链表算法实例-ag真人游戏

 自定义链表

	struct mylistnode
	{
		int nvalue;
		mylistnode *pprevnode;
		mylistnode *pnextnode;
	};
	void addtotail(mylistnode **phead,int nvalue);
void offertest::addtotail(mylistnode **phead, int nvalue)
{
	mylistnode *pnode = new mylistnode();
	pnode->nvalue = nvalue;
	pnode->pnextnode = nullptr;
	pnode->pprevnode = nullptr;
	mylistnode *pheadnode = *phead;
	if (pheadnode == nullptr)
	{
		pheadnode = pnode;
	}
	else
	{
		while (pheadnode->pnextnode != nullptr)
		{
			pheadnode = pheadnode->pnextnode;
		}
		pheadnode->pnextnode = pnode;
		pnode->pprevnode = pheadnode;
	}
}
void offertest::removenode(mylistnode **phead, int nvalue)
{
	if (*phead == nullptr || phead == nullptr)
	{
		return;
	}
	mylistnode *pheadnode = *phead;
	mylistnode *pdeletenode = nullptr;
	if (pheadnode->nvalue == nvalue)
	{
		pdeletenode = pheadnode;
		pheadnode = pheadnode->pnextnode;
		pheadnode->pnextnode->pprevnode = nullptr;
		delete pdeletenode;
		pdeletenode = nullptr;
	}
	else
	{
		while (pheadnode->pnextnode != nullptr && pheadnode->pnextnode->nvalue != nvalue)
		{
			pheadnode = pheadnode->pnextnode;
		}
		if (pheadnode->pnextnode != nullptr && pheadnode->pnextnode->nvalue == nvalue)
		{
			pdeletenode = pheadnode->pnextnode;
			pheadnode->pnextnode = pheadnode->pnextnode->pnextnode;
			pheadnode->pnextnode->pnextnode->pprevnode = pheadnode;
			delete pdeletenode;
			pdeletenode = nullptr;
		}
	}
}

在 o(1) 时间内删除链表节点

① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 o(1)。

② 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 o(n)。

综上，如果进行 n 次操作，那么大约需要操作节点的次数为 n-1 n=2n-1，其中 n-1 表示 n-1 个不是尾节点的每个节点以 o(1) 的时间复杂度操作节点的总次数，n 表示 1 个尾节点以 o(n) 的时间复杂度操作节点的总次数。(2n-1)/n ~ 2，因此该算法的平均时间复杂度为 o(1)。

	struct mylistnode
	{
		int nvalue;
		mylistnode *pprevnode;
		mylistnode *pnextnode;
	};
	void deletenode(mylistnode **phead, mylistnode *tobedelete);
void offertest::deletenode(mylistnode **phead, mylistnode *tobedelete)
{
	if (phead == nullptr || *phead == nullptr || tobedelete == nullptr)
		return;
	if (tobedelete->pnextnode != nullptr) //要删除的节点不是尾节点
	{
		mylistnode *pnext = tobedelete->pnextnode;
		tobedelete->nvalue = pnext->nvalue;
		tobedelete->pnextnode = pnext->pnextnode;
		delete pnext;
		pnext = nullptr;
	}
	else if (*phead == tobedelete)//只有一个节点
	{
		delete tobedelete;
		tobedelete = nullptr;
		*phead = nullptr;
	}
	else//链表有多个节点，删除尾结点
	{
		mylistnode *pcur = *phead;
		while (pcur->pnextnode != tobedelete)
			pcur = pcur->pnextnode;
		pcur->pnextnode = nullptr;
		delete tobedelete;
		tobedelete = nullptr;
	}
}

从尾到头打印链表

使用栈先进后出的思维

void reverseprint(mylistnode *phead);//倒序打印
void offertest::reverseprint(mylistnode *phead)
{
	if (phead == nullptr )
	{
		return;
	}
	std::stacknodes;
	mylistnode *pheadnode = phead;
	while (pheadnode != nullptr)
	{
		nodes.push(pheadnode);
		pheadnode = pheadnode->pnextnode;
	}
	while (nodes.empty() == false)
	{
		pheadnode = nodes.top();
		std::cout << pheadnode->nvalue << std::endl;
		nodes.pop();
	}
}

求链表倒数第k个节点

//使用2个指针，遍历一次链表即可。当第一个指针到达k处时，第二个指针开始移动。直到第一个指针到达尾部。
mylistnode *findk(mylistnode *phead, int k);
offertest::mylistnode * offertest::findk(mylistnode *phead, int k)
{
	if (phead == nullptr || k <=0 )
	{
		return nullptr;
	}
	mylistnode *phead1 = phead;
	mylistnode *phead2 = phead;
	for (int i = 0; i < k-1; i  )
	{
		if (phead1->pnextnode != nullptr)
		{
			phead1 = phead1->pnextnode;
		}
		else
		{
			return nullptr;
		}	
	}
	while (phead1->pnextnode != nullptr)
	{
		phead1 = phead1->pnextnode;
		phead2 = phead2->pnextnode;
	}
	return phead2;
}

反转链表

mylistnode* reverselist(mylistnode *phead);
offertest::mylistnode* offertest::reverselist(mylistnode *phead)
{
	mylistnode *preversehead = nullptr;
	if (phead == nullptr)
	{
		return preversehead;
	}
	mylistnode *pnode = phead;
	mylistnode *pprevnode = nullptr;
	while (pnode != nullptr)
	{
		mylistnode *pnextnode = pnode->pnextnode;
		if (pnextnode == nullptr)
		{
			preversehead = pnode;
		}
		pnode->pnextnode = pprevnode;
		pprevnode = pnode;
		pnode = pnextnode;
	}
	return preversehead;
}

合并链表

mylistnode* mergelist(mylistnode *phead1, mylistnode *phead2);
offertest::mylistnode* offertest::mergelist(mylistnode *phead1, mylistnode *phead2)
{
	if (phead2 == nullptr)
	{
		return phead1;
	}
	if (phead1 == nullptr)
	{
		return phead2;
	}
	mylistnode *pmergenode = nullptr;
	if (phead1->nvalue < phead2->nvalue)
	{
		pmergenode = phead1;
		pmergenode->pnextnode = mergelist(phead1->pnextnode, phead2);
	}
	else
	{
		pmergenode = phead2;
		pmergenode->pnextnode = mergelist(phead1, phead2->pnextnode);
	}
	return pmergenode;
}