算法通过村第二关-链表白银笔记
文章目录
- 再战链表|反转链表
- 剑指 Offer II 024. 反转链表
- 熟练掌握这两种解法
- 建立头节点的解决思路
- 不采用建立头节点的方法
- 采用循环/递归的方式解决
- 总结
再战链表|反转链表
提示：多拿些酒来，因为生命只有乌有。
剑指 Offer II 024. 反转链表
如果不使用链表的话，很快就能让他反转，不过也没有那么简单（用链表的话🥰）
熟练掌握这两种解法
建立头节点的解决思路
拿到题目，想一想怎么处理最好💡
那我们就先画个图吧💕
再来个过程图，这让就看的懂了：
- 建立一个头节点指向 1
- cur 直线待处理的头节点
- 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😁
注意：链表的结构
我们来看一下执行期间的流程图：
- 开始prev指向null cur 指向头节点 next 指向下一个节点
- 这样从cur 开始把链表切成两段 修改cur后面的指针域
- cur.next = pre; pre = cur; cur = next; 完成替换
注意：上面👆的代码太重要了，建议理解的基础上，刻在骨子里，以后用的地方很多。
采用循环/递归的方式解决
这个放到后面解决，目前先不讨论。
总结
这里最主要的是掌握链表反转，【不带头节点的】⭐