LeetCode 反转链表 [简单]
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
题目分析
解答1
使用外部空间 先把数据拿出来，然后再把数据放回去
解答2
双指针迭代
请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
动画演示如下
解答3
递归解法
以上解法来自：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/dong-hua-yan-shi-duo-chong-jie-fa-206-fan-zhuan-li/
代码实现
public class ReverseList {
public static ListNode reverseList2(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = reverseList2(head.next);
head.next.next = head;
head.next = null;
return cur;
}
public static ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head, tmp = null;
while (cur != null) {
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
