剑指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;
        
    }
};