Leetcode 2020春招必刷61题-2
题目：反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
1、迭代方法：我们可以维护两个指针，第一个指针pre初始化为空指针，第二个指针cur指向链表头节点head。只要cur指针不为空，就将cur.next指向pre，然后cur和pre各向后移动一位。这样当cur指针遍历完成整个链表时，pre就指向反转后链表的第一个元素。
2、递归方法：
递归方法相对比较抽象，借用leetcode评论区大佬的解释~
举例：假设链表是[1, 2, 3, 4, 5]从最底层最后一个reverseList(5)来看
···返回了5这个节点
···reverseList(4)中
···p为5
···head.next.next = head 相当于 5 -> 4
···现在节点情况为 4 -> 5 -> 4
···head.next = null,切断4 -> 5 这一条，现在只有 5 -> 4
···返回（return）p为5，5 -> 4
···返回上一层reverseList(3)
···处理完后返回的是4 -> 3
···依次向上
代码：
1、迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
2、递归
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
