# 问题 原题链接：[https://leetcode.com/problems/reverse-linked-list/](https://leetcode.com/problems/reverse-linked-list/) Reverse a singly linked list. Example: ``` Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL ``` Follow up: - A linked list can be reversed either iteratively or recursively. Could you implement both? # 分析过程 - 输入：一个链表 - 输出：一个反向链表 - 思路：循环方法，拷贝链表时反向指针即可。递归方法，递归找到最后一个节点，递归返回时候翻转指向。 # 解决方法 方法1： ```cpp class Solution { public: ListNode* reverseList(ListNode* head) { if (!head) { return nullptr; } ListNode *newPre = new ListNode(head->val); ListNode *newTmp = nullptr; ListNode *tmp = head->next; while (tmp) { newTmp = new ListNode(tmp->val); newTmp->next = newPre; newPre = newTmp; tmp = tmp->next; } return newPre; } }; ``` 方法2： ```cpp class Solution { public: ListNode *_reverseList(ListNode *head) { if (!head || !head->next) { return head; } // 和返回值一起看，达到递归条件时候，newRoot就是原链表的最后一个 // root会随着递归返回，从倒数第二个开始一个一个往前移 ListNode *newRoot = _reverseList(head->next); // 翻转指向 // 原：3 - 4 - 5 // 现：3 - 4 - 3 // 下一步：2 - 3 - 4 -> 2 - 3 - 2 // 一直到：0 - 1 - 2 -> 0 - 1 - 0 head->next->next = head; // 3 - 4 - 3，成环，把环打断变成 4 - 3 - null // 下一步：3 - 2 - 3 -> 3 - 2 - null head->next = nullptr; return newRoot; } ListNode *reverseList(ListNode *head) { if (!head) { return nullptr; } // 先拷贝一份 ListNode *newRoot = new ListNode(head->val); ListNode *newTmp = newRoot; ListNode *tmp = head->next; while (tmp) { newTmp->next = new ListNode(tmp->val); newTmp = newTmp->next; tmp = tmp->next; } // 反向 return _reverseList(newRoot); } }; ```