每天一道算法題41-反轉連結清單

除了使用棧的特性或者另外開辟記憶體從後往前拷貝，另外有兩種方法,分别是遞歸法和周遊法，其中周遊法更加節省記憶體，遞歸法寫起來邏輯簡單。

周遊法用圖來表示：

遞歸法用圖來表示：

詳細邏輯可以參考：Java單連結清單反轉 詳細過程

代碼如下：

#include "iostream"
struct NODE_T
{
	int data;
	struct NODE_T* pdata;
};

//1.遞歸反轉法
NODE_T* reverse1(NODE_T* head)
{
	if (NULL==head->pdata)
	{
		return head;
	}

	NODE_T* rHead = reverse1(head->pdata);
	head->pdata->pdata = head;
	head->pdata = NULL;
	return rHead;
}

//2.周遊反轉法
NODE_T* reverse2(NODE_T* head)
{
	if (NULL == head->pdata)
	{
		return head;
	}

	NODE_T* pCurrent,*pNext,*pBefore;
	pCurrent = head;
	pNext = pCurrent->pdata;
	pBefore = NULL;
	while (NULL != pNext)
	{
		pCurrent->pdata = pBefore;
		pBefore = pCurrent;

		pCurrent = pNext;
		pNext = pCurrent->pdata;
	}

	pCurrent->pdata = pBefore;

	return pCurrent;
}

void main()
{
	//1.initiation
	NODE_T nodes[10];
	for (int i = 0; i < 10; i++)
	{
		nodes[i].data = i;
		nodes[i].pdata = i == 9 ? NULL : &nodes[i+1];
	}
	NODE_T* head = nodes;
	printf("\n before:");
	while (head !=NULL)
	{
		printf("%d,",head->data);
		head = head->pdata;
	}

	//2.reverse1
	if (0)
	{
		head = reverse1(nodes);
		printf("\n aftrer:");
		while (head != NULL)
		{
			printf("%d,", head->data);
			head = head->pdata;
		}
	}
	else
	{
		//3.reverse2
		head = reverse2(nodes);
		printf("\n aftrer:");
		while (head != NULL)
		{
			printf("%d,", head->data);
			head = head->pdata;
		}
	}

	return;
}