反转链表

反转链表(递归实现)/*
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;
         
        //先反转后面的链表，走到链表的末端结点
        ListNode* pReverseNode=ReverseList(pHead->next);
         
        //再将当前节点设置为后面节点的后续节点
        pHead->next->next=pHead;
        pHead->next=NULL;
         
        return pReverseNode;

    }
};
反转链表(栈)

	/*


	struct ListNode {


	    int val;


	    struct ListNode *next;


	    ListNode(int x) :


	            val(x), next(NULL) {


	    }


	};*/


	classSolution {


	public:


	    ListNode* ReverseList(ListNode* pHead) {


	        if(pHead==NULL || pHead->next==NULL)


	            returnpHead;


	        ListNode* p=pHead;


	        stack<ListNode* > s;


	        while(p->next){


	            s.push(p);


	            p=p->next;


	        }


	        ListNode* q=p;


	        while(!s.empty()){


	            p->next=s.top();


	            p=p->next;


	            s.pop();


	        }


	        p->next=NULL;


	        returnq;


	 


	    }


	};