链表算法实例

 自定义链表

	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::stack<MyListNode*>nodes;
	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;
}