剑指Offer 反转链表

题目描述

输入一个链表，反转链表后，输出链表的所有元素。

思路：

法1：用栈，压栈出栈

法2：头插法（有递归非递归2中）

AC代码：

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* ReverseList(ListNode* pHead) {
12         if(pHead==NULL||pHead->next == NULL)
13         {
14             return pHead;
15         }
16         
17         ListNode *q=pHead;
18         ListNode *newHead;
19         
20         stack<ListNode*> stack1;
21         
22         while(q->next!=NULL)
23         {
24             stack1.push(q);
25             q=q->next;
26         }
27         newHead = q;
28         
29         while(!stack1.empty())
30         {
31             q->next=stack1.top();
32             q=q->next;
33             stack1.pop();
34         }
35         q->next=NULL;
36         return newHead;      //返回新的头节点
37     }
38 };