行百里者半九十 —— 链表（1）

原题链接：

1----
2----

1、输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

使用反向迭代器

 1  struct ListNode{
 2   int val;
 3   ListNode *next;
 4   ListNode(int x):val(x),next(NULL){}
 5 };
 6 
 7 class Solution{
 8 public:
 9     vector<int> reversePrint(ListNode* head){
10         int length = 0;
11         //链表为空则直接返回
12         if(head == nullptr) return vector<int>();
13         ListNode* ptr = head;
14         //计算链表长度
15         while(ptr->next != nullptr) {
16             length++;
17             ptr = ptr->next;
18         }
19         vector<int> vec(length+1);
20         ptr = head;
21         //利用反向迭代器，将元素填入数组
22         for(auto i = vec.rbegin(); i != vec.rend(); ++i){
23             *i = ptr->val;
24             ptr = ptr->next;
25         }
26         return vec;
27     }
28 };

2、定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

修改节点指针的指向即可

 1  // 1->2->3   1<-2<-3
 2 class Solution{
 3 public:
 4     ListNode* reverseList(ListNode* head){
 5         ListNode *curNode = head;
 6         ListNode *preNode = nullptr;
 7         while(curNode != nullptr){
 8             ListNode* tmp = curNode->next;
 9             curNode->next = preNode;
10             preNode = curNode;
11             curNode = tmp;
12         }
13         return preNode;
14     }
15 };