上节我们通过一个梁山好汉排行傍的案例分析了单链表的基本用法，这节我们通过一个经典的面试题来加深对单链表的学习，不扯了直接看正题
经典面试题
题目
- 单链表的反转问题
本片的讲解是基于我们对前面链表熟悉的基础上来加深印象，先来分析单链表是如何反转的，百度一大堆，但我个人绝得不适合像我这种入门的小白，下面是我的思路分析，先来看一张图：
单链表反转1.png
- 简单的讲解下：
- 上面一行是我之前原来的链表，我经过某一种方式最后将链表反转成下面这个样子
-我的思路：
1). 首先我可以定义一个新的节点如：HeroNode reverseNode = new HeroNode();当然它只代表新的头结点，不做数据的任何存储.
2). 接着从头到尾遍历原来的链表，每遍历一个节点将其取出并放在reverseNode头结点的next个，
3). 将原来链表的head.next 指向reverseNode.next,这样就完成了链表的反转
看似简单的三步分析，但实际用代码实现还是有点难度的，接下来我们来看代码实现。
代码实现
//单链表反转
public static void reverseLinkList(HeroNode head){
//首先是判断链表是否为null或者链表是否只有一个节点
if (head.next == null || head.next.next == null){
return;
}
//定义一个辅助指针(变量)，遍历原先的链表
HeroNode cur = head.next;
HeroNode next = null; //指向当前节点的下一个(主要做的原因是当我们遍历到当前节点cur时，需要取出当前节点，为了防止链表断开所以需要定义一个next来指向当前节点的下一个节点)
HeroNode reverseHead = new HeroNode(0,"",""); //空的节点头
//2.遍历原来的链表，每遍历一个节点，将其取出放在reverseHead的最前端
while (cur !=null){
next = cur.next;//先暂时的保存当前(cur)节点的下一个节点，主要的目的是后面的需要
cur.next = reverseHead.next; //将当前节点的下一个节点指向reverseHead的下一个
reverseHead.next = cur ; //将cur链接到新的链表中
cur = next; //后移接着遍历
}
//将原来的head的下一个指向reverseHead的下一个节点实现单链表的反转
head.next = reverseHead.next;
}
代码的关键是在while的循环里，就这样通过三步实现了链表的反转，因为链表反转是不包含头部节点的反转的，代码注释很详细，我们来看测试的过程：
测试代码
public class SingleLinkListCase {
public static void main(String[] args) {
//创建节点
HeroNode node1 = new HeroNode(1,"宋江","及时雨");
HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
HeroNode node3 = new HeroNode(3,"吴用","智多星");
HeroNode node4 = new HeroNode(4,"林冲","豹子头");
//创建链表，并添加
SingleLinkList singleLinkList = new SingleLinkList();
singleLinkList.addOrderByNo(node1);
singleLinkList.addOrderByNo(node4);
singleLinkList.addOrderByNo(node2);
singleLinkList.addOrderByNo(node3);
//显示链表
singleLinkList.show();
//测试：链表反转测试
System.out.println("反转之后============================");
reverseLinkList(singleLinkList.getHead());
singleLinkList.show();
测试结果如图所示：
image.png
上图是反转前后的对比，很显然，我们实现了链表的反转，世上算法万千，简单易懂的却在这里，嘻嘻嘻.....,同样这也是一道大厂的面试题
网友评论