单链表反转-腾讯面试题-图解
文章目录
- 单链表反转
- 思路
- 第一步,定义reverseHead
- 第二步,从头到尾遍历原来的链表,取出节点,并放在新链表reverseHead 的最前端
- 1.取出第一个
- 2.取出第二个
- 3.取出第三个
- 第三步,原来的链表的head.next = reverseHead.next
- 代码
- 代码分析
- 插入操作
- 判断是否为空
- 参考资料
单链表反转
题目将单链表反转
代码
//定义HeroNode , 每个HeroNode 对象就是一个节点
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next; //指向下一个节点
//构造器
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
//为了显示方法,我们重新toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
思路
1. 先定义一个节点 reverseHead = new HeroNode();
2. 从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead 的最前端.
3. 原来的链表的head.next = reverseHead.next
第一步,定义reverseHead
定义reverseHead
第二步,从头到尾遍历原来的链表,取出节点,并放在新链表reverseHead 的最前端
1.取出第一个
2.取出第二个
3.取出第三个
第三步,原来的链表的head.next = reverseHead.next
代码
//将单链表反转
public static void reversetList(HeroNode head) {
//如果当前链表为空,或者只有一个节点,无需反转,直接返回
if(head.next == null || head.next.next == null) {
return ;
}
//定义一个辅助的指针(变量),帮助我们遍历原来的链表
HeroNode cur = head.next;
HeroNode next = null;// 指向当前节点[cur]的下一个节点
HeroNode reverseHead = new HeroNode(0, "", "");
//遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead 的最前端
//动脑筋
while(cur != null) {
next = cur.next;//先暂时保存当前节点的下一个节点,因为后面需要使用
cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
reverseHead.next = cur; //将cur 连接到新的链表上
cur = next;//让cur后移
}
//将head.next 指向 reverseHead.next , 实现单链表的反转
head.next = reverseHead.next;
}
代码分析
插入操作
单链表的反转其实用到了单链表插入的知识点,而单链接插入时,需要注意下面这样插入是错误的。
reverseHead.next = cur;
cur.next = reverseHead.next;
如果先执行reverseHead.next = cur;
后面的链表就断开了。
判断是否为空
while(cur != null) {
next = cur.next;//先暂时保存当前节点的下一个节点,因为后面需要使用
//----------------------------------//
//----------------------------------//
cur = next;//让cur后移
}
这里是先判断当前节点current,缩写为cur,是否为空,不为空,就不断循环。
然后将cur.next
放到一个变量中,以防止插入的操作影响到cur.next
变量。
然后是中间的插入操作(或者是其它的操作)。
然后将cur后移。怎么后移呢,我们在插入操作
前,保存了cur的下一个节点的信息在next变量里面,
这时,只需要把next变量里面的值给回cur就实现了后移的操作。
后移之后,再想要进入循环,会被while
拦住,它会问你,是不是空? 如果是空,那这说明已经循环遍历
完所有的节点了。如果不是空,那说明,还有节点没有遍历完,继续进入里面执行。
参考资料
参考资料1—022-老韩-单链表腾讯面试题
参考资料2—单链表按顺序插入节点