脚撕LeetCode(206)Easy
脚撕LeetCode(206)Easy
题目地址：https://leetcode-cn.com/problems/reverse-linked-list/
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}因为做到面试题0206提示说要先做206，所以就先做了206.
其实206的题意很简单，就是单向链表的反转
一、爆破法（迭代）
爆破法想到的就是，保留当前指针，保留next指针，保留next的next指针。然后next指向当前（如果当前是首指针的话他的next要先滞空），然后head指向next，next指向next.next,然后继续往下，周而复始直到next == null
执行结果如下：
28 / 28 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 38.2 MB
public static ListNode reverseListMe(ListNode head) {
if (null == head)return null;
ListNode next = head.next;
head.next = null;
ListNode waitNode;
while (null != next) {
waitNode = next.next;
next.next = head;
head = next;
if(null == waitNode) {
break;
}
next = waitNode;
}
return head;
}时间是100%，但是空间是60%，免不了要翻官方答案，发现官方的思路很巧妙，而且把很多步骤抽取的规则化了，很少单独对指定某个节点进行操作
二、官方答案，迭代法
没什么好讲的，思路差不多，执行结果也是一样的，不同的是没有单独对head做判断，而是在一开始定值的时候就设定了。
执行结果如下：
28 / 28 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 38.3 MB
public ListNode reverseList2(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}三、官方递归法
这里是递归，我们直接设想最里层的结果
比如传入1，2，3，4，5
那么最里层先返回5，然后出栈，然后是4的next的next 也就是5的next指向4，然后4的next指向null，弹出5->4
然后是到1->2->3中的3出栈，然后3的next4的next指向3，3的next指向null，然后弹出5->4->3，
然后是1->2中的2出栈，2的next的next也就是3的next指向2，然后2的next=null，弹出5->4->3->2
最后，1的next的next也就是2的next指向1，1的next指向null，完全出栈5->4->3->2->1
执行结果如下：
28 / 28 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 38.6 MB
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}虽然有想过递归，但是暂时没什么想法，可能是之前数组，循环，字符串写的比较多，后续需要对递归和树这一块加强一下。