劍指offer之面試題16 ：反轉鏈表

題目:輸入一個鏈表，反轉鏈表后，輸出鏈表的所有元素。

思路一：利用棧的后進先出

代碼：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
        //利用棧的后進先出的特點，最后進的最先出
		stack<int> s1;
        ListNode *p=pHead;
        //將鏈表中的每個元素的值進行壓棧
        while(p!=NULL)
        {
            s1.push(p->val);
            p=p->next;
        }
        //出棧，并且將棧頂元素放入鏈表中
        p=pHead;
        while(!s1.empty())
        {
            p->val=s1.top();
            s1.pop();
            p=p->next;
        }
        return pHead;
    }
};

思路二：進行摘結點，然后頭插

代碼：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
        if(pHead==NULL)
        {
            return NULL;
        }
	ListNode *newHead=NULL;
        ListNode *cur=pHead;
        ListNode *tmp=NULL;
        while(cur!=NULL)
        {
            tmp=cur;
            //關鍵點：一定要讓cur先往后走,再進行插入操作
            //不然會讓原鏈表找不到后面的結點，結果就會變成只有一個結點
            cur=cur->next;
            tmp->next=newHead;
            newHead=tmp;
        }
        return newHead;
    }
};

思路三：利用遞歸，找到最后一個結點作為函數的返回值，然后在改變該鏈表的每一個當前pHead的位置

代碼：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
		//終止條件
        if(pHead==NULL||pHead->next==NULL)
        {
            return pHead;
        }
        //newHead得到對應的返回值，尾節點
        ListNode *newHead=ReverseList(pHead->next);
        //然后將當先棧幀中的pHead的next進行更改
        //比如說1->2->3->4->NULL
        //newHead->4
        //pHead->3
        //4->3->null
        //此時指向3的還有1->2->3->null
		pHead->next->next=pHead;
        pHead->next=NULL;
        return newHead;
        
    }
};