遞歸和非遞歸實作連結清單反轉

連結清單反轉是面試筆試常考題目，直接貼代碼。

反轉函數如下:

//思路為将節點從前到後依次放到表頭，最後最後的節點到了最前面,最前面的節點到了最後面
ListNode * ReverseList(ListNode *  head)
{
   //如果連結清單為空或者連結清單中隻有一個元素
   if(head==NULL || head->m_pNext==NULL)
	   return head;
   ListNode * p=head->m_pNext;
   ListNode * q=head;
   while(p!=NULL)
   {
     q->m_pNext=p->m_pNext;//記錄下p的下一個節點
	 p->m_pNext=head;
	 head=p;
	 p=q->m_pNext;//準備将p的下一個節點放到表頭
   }
   return head;
}

//遞歸方式
ListNode * ReverseList2(ListNode * head)
{
	//如果連結清單為空或者連結清單中隻有一個元素
	if(head==NULL || head->m_pNext==NULL)
		return head;
	else
	{
	   ListNode * newhead=ReverseList2(head->m_pNext);//先反轉後面的連結清單
	   head->m_pNext->m_pNext=head;//再将目前節點設定為其然來後面節點的後續節點
	   head->m_pNext=NULL;
	   return newhead;
	}
}      

整體測試代碼如下:

// 反轉連結清單.cpp : 定義控制台應用程式的入口點。
#include "stdafx.h"
#include  <iostream>
using namespace std;

//定義一個連結清單節點
 typedef struct ListNode
{
	int       m_nKey;
	struct ListNode * m_pNext;
}ListNode;

//插入一個新節點到連結清單中(放在連結清單頭部)
void CreateList(ListNode * & head,int data)
{
	//建立新節點
    ListNode * p=(ListNode*)malloc(sizeof(ListNode));
	p->m_nKey=data;
	p->m_pNext=NULL;

	if(head==NULL)
	{
		head=p;
		return;
	}
	p->m_pNext=head;
	head=p;
}

void  printList(ListNode* head)
{
   ListNode * p=head;
   while(p!=NULL)
   {
      cout<<p->m_nKey<<" ";
	  p=p->m_pNext;
   }
   cout<<endl;
}

//思路為将節點從前到後依次放到表頭，最後最後的節點到了最前面,最前面的節點到了最後面
ListNode * ReverseList(ListNode *  head)
{
   //如果連結清單為空或者連結清單中隻有一個元素
   if(head==NULL || head->m_pNext==NULL)
	   return head;
   ListNode * p=head->m_pNext;
   ListNode * q=head;
   while(p!=NULL)
   {
     q->m_pNext=p->m_pNext;//記錄下p的下一個節點
	 p->m_pNext=head;
	 head=p;
	 p=q->m_pNext;//準備将p的下一個節點放到表頭
   }
   return head;
}

//遞歸方式
ListNode * ReverseList2(ListNode * head)
{
	//如果連結清單為空或者連結清單中隻有一個元素
	if(head==NULL || head->m_pNext==NULL)
		return head;
	else
	{
	   ListNode * newhead=ReverseList2(head->m_pNext);//先反轉後面的連結清單
	   head->m_pNext->m_pNext=head;//再将目前節點設定為其然來後面節點的後續節點
	   head->m_pNext=NULL;
	   return newhead;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	ListNode * Head=NULL;
    for(int i=0;i<10;i++)
      CreateList(Head,i);
    printList(Head);
    Head=ReverseList(Head);
    printList(Head);
	system("PAUSE");
	return 0;
}
      

運作結果如下: