[데이터 구조 | 검 지 Offer] 단 방향 링크 의 각종 조작 실현

//    
struct ListNode
{
	int data;
	ListNode *next;
	ListNode(int x) :data(x), next(NULL) {}
};

//         
void AddToTail(ListNode **pHead, int value)
{
	ListNode *pNew = new ListNode(value);
	assert(pNew != NULL);

	if (NULL == *pHead)//     
		*pHead = pNew;
	else
	{
		ListNode *pNode = *pHead;

		while (pNode->next)
			pNode = pNode->next;

		pNode->next = pNew;
	}
}

/*                 
                   */
void RemoveNode(ListNode **pHead, int value)
{
	if (NULL == pHead || NULL == *pHead)
		return;

	ListNode *pToDeleted = NULL;
	if ((*pHead)->data == value)
	{
		pToDeleted = *pHead;
		*pHead = (*pHead)->next;
	}
	else
	{
		ListNode *pNode = *pHead;

		while (pNode->next && pNode->next->data != value)//           
			pNode = pNode->next;

		if (pNode->next && pNode->next->data == value)
		{
			pToDeleted = pNode->next;
			pNode->next = pNode->next->next;
		}
	}

	if (pToDeleted != NULL)
	{
		delete pToDeleted;
		pToDeleted = NULL;
	}
}

//    ：  。          
void PrintReverse(ListNode *pHead)
{
	if (pHead)
	{
		PrintReverse(pHead->next);
		cout << pHead->data << endl;
	}
}

//    ： 
void PrintReverse_iteratively(ListNode *pHead)
{
	stack<ListNode *> nodes;

	ListNode *pNode = pHead;
	while (pNode)
	{
		nodes.push(pNode);
		pNode = pNode->next;
	}

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

/*
                 ，       O(1)       
                ，        
 
     ：                         ，         。
                   。                  
*/
void DeleteNode(ListNode **pHead, ListNode *pToBeDeleted)
{
	if (NULL == pHead || NULL == *pHead)
		return;

	//           
	if (pToBeDeleted->next)
	{
		ListNode *pNext = pToBeDeleted->next;
		pToBeDeleted->data = pNext->data;//          
		pToBeDeleted->next = pNext->next;

		delete pNext;
		pNext = NULL;
	}
	//        
	else if (*pHead == pToBeDeleted)
	{
		delete pToBeDeleted;
		pToBeDeleted = NULL;
		*pHead = NULL;
	}
	//       ，          
	else//         O(n)，           O(1)
	{
		ListNode *pNode = *pHead;
		while (pNode->next != pToBeDeleted)
			pNode = pNode->next;

		pNode->next = NULL;
		delete pToBeDeleted;
		pToBeDeleted = NULL;
	}
}

/*      ，          k    
   ： */
ListNode* PrintKNode(ListNode *pHead, int k)
{
	if (NULL == pHead || k < 1)
		return NULL;

	stack<ListNode *> nodes;
	ListNode *pNode = pHead;
	while (pNode)
	{
		nodes.push(pNode);
		pNode = pNode->next;
	}

	while (!nodes.empty())
	{
		--k;
		if (0 == k)
		{
			pNode = nodes.top();
			return pNode;
		}
		nodes.pop();
	}
	return NULL;
}
/*   ：    。          k-1，          ，         k   */
ListNode* FindKthToTail(ListNode *pHead, int k)
{
	if (NULL == pHead || k < 1)
		return NULL;

	ListNode *pAhead = pHead;
	ListNode *pBehind = NULL;

	for (int i = 0; i < k - 1; ++i)
	{
		if (pAhead->next)
			pAhead = pAhead->next;
		else
			return NULL;
	}

	pBehind = pHead;
	while (pAhead->next)
	{
		pAhead = pAhead->next;
		pBehind = pBehind->next;
	}

	return pBehind;
}

/*    :          ，                 
        ，              */
ListNode* ReverseList(ListNode *pHead)
{
	if (NULL == pHead || pHead->next == NULL)
		return pHead;

	ListNode *pPrev = NULL;
	ListNode *pNode = pHead;
	while (pNode)
	{
		ListNode *pNext = pNode->next;

		pNode->next = pPrev;
		pPrev = pNode;//            
		pNode = pNext;
	}	
	return pPrev;
}

/*         ，            （  ）*/
/*                 ，             ，             。
    ，                    */
ListNode* MergeList(ListNode *pHead1, ListNode *pHead2)
{
	if (NULL == pHead1)
		return pHead2;
	else if (NULL == pHead2)
		return pHead1;

	ListNode *pMergedHead = NULL;

	if (pHead1->data < pHead2->data)
	{
		pMergedHead = pHead1;
		pMergedHead->next = MergeList(pHead1->next, pHead2);
	}
	else
	{
		pMergedHead = pHead2;
		pMergedHead->next = MergeList(pHead1, pHead2->next);
	}
	return pMergedHead;
}

/*      ，            
    L1 6   ，L2 4   ，         mn1*/
/*
L1:   n1 -> n2 -> n3 -> n4   
                          \
						   ——> mn1 -> mn2
						  /
L2:               m1 -> m2
*/
/*
    ：                    ，      
        
*/
int GetLength(ListNode *pHead)
{
	int leng = 0;
	while (pHead)
	{
		leng++;
		pHead = pHead->next;
	}
	return leng;
}

ListNode* FindFirstCommonNode(ListNode *L1, ListNode *L2)
{
	if (NULL == L1 || NULL == L2)
		return NULL;
	int leng1 = GetLength(L1);
	int leng2 = GetLength(L2);

	int distance = (leng1 > leng2) ? leng1 - leng2 : leng2 - leng1;
	ListNode *pFirst = NULL, *pSecond = NULL;
	if (leng1 > leng2)
	{
		pFirst = L1;
		pSecond = L2;
	}
	else
	{
		pFirst = L2;
		pSecond = L1;
	}
		
	while (distance--)//             
	{
		pFirst = pFirst->next;
	}

	while (pFirst && pSecond)
	{
		if (pFirst == pSecond)//         
			return pFirst;
		pFirst = pFirst->next;
		pSecond = pSecond->next;
	}
	return NULL;//         
}

/*         
     ：    ，            ，
        ：http://blog.csdn.net/wenqian1991/article/details/17452715 */
ListNode* EntryNodeOfLoop(ListNode *pHead)
{
	if (NULL == pHead)
		return NULL;

	ListNode *pFast = pHead;
	ListNode *pSlow = pHead;

	//      
	while (pFast->next)//        
	{
		pFast = pFast->next->next;
		pSlow = pSlow->next;
		
		if (NULL == pFast)
			return NULL;
		if (pFast == pSlow)//  
			break;
	}

	if (NULL == pFast->next)//  
		return NULL;

	//        
	/*           ，                      
	http://blog.csdn.net/wenqian1991/article/details/17452715 */
	pFast = pHead;
	while (pFast != pSlow)
	{
		pFast = pFast->next;
		pSlow = pSlow->next;
	}

	return pFast;
}