一、链表

#pragma once

struct ListNode
{
	int value;
	ListNode *pNext;
};

// 在链表末尾添加一个节点
void AddToTail(ListNode** pHead, int value);

// 找到链表中第一个含有某值的节点并删除
void RemoveFirstNode(ListNode** pHead, int value);

// 从尾到头打印链表
void printReversingly_Iteratively(ListNode* pHead);

// 反转链表
ListNode* ReverseLinkedList(ListNode* pHead);

// 合并两个有序链表
ListNode* MergeLinkedList(ListNode* pHead1, ListNode* pHead2);

// 链表中倒数第k个节点
ListNode* GetReverseKNode(ListNode* pHead, int k);

// 两个链表第一个公共节点
ListNode* FirstCommonNode(ListNode* pHead1, ListNode* pHead2);

#include "LinkedList.h"
#include <stack>
#include <iostream>

// 在链表末尾添加一个节点
void AddToTail(ListNode** pHead, int value)
{
	// 新节点定义
	ListNode* pNew = new ListNode();
	pNew->value = value;
	pNew->pNext = nullptr;

	if (nullptr == pHead)
	{
		*pHead = pNew;
	}
	else
	{
		ListNode* pNode = *pHead;// 此处定义一个游标指针，用于自由移动。
		while (pNode->pNext != nullptr)
		{
			pNode = pNode->pNext;
		}
		pNode->pNext = pNew;
	}
}

// 找到链表中第一个含有某值的节点并删除
void RemoveFirstNode(ListNode** pHead, int value)
{
	if (nullptr == pHead || nullptr == *pHead)
	{
		return;
	}

	ListNode* pToBeDeleted = nullptr;
	if ((*pHead)->value == value)// 在表头找到该值
	{
		pToBeDeleted = *pHead;
		*pHead = (*pHead)->pNext;
	}
	else
	{
		ListNode* pNode = *pHead;
		while (pNode->pNext != nullptr && pNode->pNext->value != value)
		{
			pNode = pNode->pNext;
		}
		if (pNode->pNext != nullptr && pNode->pNext->value == value)
		{
			pToBeDeleted = pNode->pNext;
			pNode->pNext = pNode->pNext->pNext;
		}
	}

	if (nullptr != pToBeDeleted)
	{
		delete pToBeDeleted;
		pToBeDeleted = nullptr;
	}
}

// 从尾到头打印链表(用栈实现)
void printReversingly_Iteratively(ListNode* pHead)
{
	std::stack<ListNode*> nodes;
	ListNode* pNode = pHead;
	while (nullptr != pNode)
	{
		nodes.push(pNode);
		pNode = pNode->pNext;
	}

	while (!nodes.empty())
	{
		pNode = nodes.top();
		std::cout << pNode->value << std::endl;
		nodes.pop();
	}
}

// 反转链表
ListNode* ReverseLinkedList(ListNode* pHead)
{
	ListNode* pReversedHead = nullptr;
	ListNode* pPrev = nullptr;

	ListNode* pNode = pHead;
	while (nullptr != pNode)
	{
		ListNode* pNext = pNode->pNext;
		if (nullptr == pNext)
		{
			pReversedHead = pNode;
		}
		pNode->pNext = pPrev;
		pPrev = pNode;
		pNode = pNext;
	}
	return pReversedHead;
}

ListNode * MergeLinkedList(ListNode * pHead1, ListNode * pHead2)
{
	if (nullptr == pHead1)
	{
		return pHead2;
	}
	else if (nullptr == pHead2)
	{
		return pHead1;
	}

	ListNode* pMergedHead = nullptr;
	if (pHead1->value < pHead2->value)
	{
		pMergedHead = pHead1;
		pMergedHead->pNext = MergeLinkedList(pHead1->pNext, pHead2);
	}
	else
	{
		pMergedHead = pHead2;
		pMergedHead->pNext = MergeLinkedList(pHead1, pHead2->pNext);
	}
	return pMergedHead;
}

ListNode * GetReverseKNode(ListNode * pHead, int k)
{
	return nullptr;
}

ListNode * FirstCommonNode(ListNode * pHead1, ListNode * pHead2)
{
	return nullptr;
}