算法通过村第二关-链表白银笔记

---

再战链表|反转链表

提示：多拿些酒来，因为生命只有乌有。

---

剑指 Offer II 024. 反转链表

如果不使用链表的话，很快就能让他反转，不过也没有那么简单（用链表的话🥰）

熟练掌握这两种解法

建立头节点的解决思路

拿到题目，想一想怎么处理最好💡
那我们就先画个图吧💕

再来个过程图，这让就看的懂了：

1. 建立一个头节点指向 1
2. cur 直线待处理的头节点
3. next 直线cur 的下一个节点

我们尝试写一下代码👌
重点理解一下 图

/*** 方法1：虚拟结点 ,并复用已有的结点** @param head* @return*/
public static ListNode reverseListByDummyNotCreate(ListNode head) {if(head == null){return null;}ListNode ans = new ListNode(-1);ListNode cur = head;while(cur != null){ListNode next = cur.next; // 所以这里 需要保留一下cur后面的节点// ans.next = cur.next;// ans.next = cur;   不能这样写cur.next = ans.next;  // 改变当前节点的指针域 也就是说 现在cur后面的已经断了// 现在可以说 有两个指针指向 ans 的下一个节点ans.next = cur; // 更改指针域  下一个 ans 就不指向头节点了cur = next;  // 修改cur当前节点  进行下一次循环}return ans.next;
}

这个是经典的解决方法，很常用，一定要数量掌握。

不采用建立头节点的方法

因为上面的方法更容易想到，一般面试官也不建议使用头节点😒，不使用头节点更体现你对链表的熟悉程度。
那我们就来挑战一下😁：
我们梳理一下思路：
先画个图hahah😁

注意：链表的结构
我们来看一下执行期间的流程图：

1. 开始prev指向null cur 指向头节点 next 指向下一个节点
2. 这样从cur 开始把链表切成两段 修改cur后面的指针域
3. cur.next = pre; pre = cur; cur = next; 完成替换

注意：上面👆的代码太重要了，建议理解的基础上，刻在骨子里，以后用的地方很多。

采用循环/递归的方式解决

这个放到后面解决，目前先不讨论。

---

总结

这里最主要的是掌握链表反转，【不带头节点的】⭐