206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 1 struct ListNode{
 2     int val;
 3     ListNode* next;
 4     ListNode() : val(0), next(nullptr) {}
 5     ListNode(int x) : val(x), next(nullptr) {}
 6     ListNode(int x, ListNode* next) : val(x), next(next) {}
 7 };
 8 class Solution {
 9 public:
10     ListNode* reverseList(ListNode* head) {
11         if(head == nullptr || head->next == nullptr) return head;
12         stack<ListNode*>* sta = new stack<ListNode*>();
13         ListNode* cur = head;
14         while(cur)
15         {
16             (*sta).push(cur);
17             cur = cur->next;
18         } 
19         ListNode* res = (*sta).top();
20         (*sta).pop();
21         ListNode* r = res;
22         while(!(*sta).empty())
23         {
24             r->next = (*sta).top();
25             (*sta).pop();
26             r = r->next;
27             r->next = nullptr;
28         }
29         return res;
30     }
31     ListNode* reverseList_diedai(ListNode* head){
32         if(head == nullptr || head->next == nullptr) return head;
33         ListNode* pre = nullptr;
34         ListNode* cur = head;
35         ListNode* tmp;
36         while(cur)
37         {
38             tmp = cur->next;
39             cur->next = pre;
40             pre = cur;
41             cur = tmp;
42         }
43         return pre;
44     }
45     ListNode* reverseList_digui(ListNode* head){
46         /* 这样先入递归，在修改指针，返回的会是最先进入循环的head
47             所以如果想要返回最后修改的节点，需要先修改*/
48         // if(head == nullptr || head->next == nullptr) return head;
49         // ListNode* last = reverseList_digui(head->next);
50         // if(last==head)
51         // {
52         //     last->next = nullptr;
53         // }
54         // else{
55         //     last->next = head;
56         // }
57         return reverse(NULL, head);
58     }
59     ListNode* reverse(ListNode* pre,ListNode* cur){
60         if(cur == NULL) return pre;
61         ListNode* temp = cur->next;
62         cur->next = pre;
63 
64         return reverse(cur,temp);
65     }
66 };