1.代码
1.将单向链表反向
public void reverseSetList(Heronode head) {
//判断链表是否可以反向，或没必要反向：null，或者链表长度为1，那么没有必要反向
if (head.next==null||head.next.next==null) {
System.out.println("链表长度为null或者长度为1，没有必要反向");
return;
}
//长度可以反向
//用来反向的辅助头节点
Heronode reverseHead=new HeroNode(0,"","");
//当前节点
Heronode cur = head.next;
//当前节点的下一个节点，为了不断链
Heronode curNext = null;
//遍历队列
while (cur != null) {
curNext=cur.next;//为当前节点的下一个节点赋值，目的是保证链表不断裂
cur.next=reverseHead.next;//当前节点的下一个指向赋值头节点的下一个
reverseHead.next=cur;//为赋值节点的下一个赋值
cur=curNext;//当前节点后移
}
head.next=reverseHead.next;//最后头节点指向反向节点的next
}
2.全部代码：
package com.example.lib5.linkedList;
public class SinglelinkedListDemo {
public static void main(String[] args) {
//进行测试
//先创建节点
Heronode heronode = new HeroNode(1, "唐三", "昊天宗");
Heronode heroNode1 = new HeroNode(2, "小舞", "十万年魂兽");
Heronode heroNode2 = new HeroNode(3, "宁荣荣", "七宝琉璃宗");
Heronode heroNode3 = new HeroNode(4, "千仞雪", "武魂殿");
//创建链表，并加入节点
MylinkedList mylinkedList = new MylinkedList();
// mylinkedList.add(heroNode);
// mylinkedList.add(heroNode3);
// mylinkedList.add(heroNode1);
// mylinkedList.add(heroNode2);
//根据顺序来加入节点
mylinkedList.addByOrder2(heroNode);
mylinkedList.addByOrder2(heroNode3);
mylinkedList.addByOrder2(heroNode1);
mylinkedList.addByOrder2(heroNode2);
// mylinkedList.addByOrder2(heroNode2);
// //遍历节点
mylinkedList.list();
Heronode heronodeNew = new HeroNode(3, "海女斗罗", "海神岛");
mylinkedList.update(heroNodeNew);
mylinkedList.list();
//对链表进行删除
// mylinkedList.delete(3);
mylinkedList.list();
System.out.println("面试题，获取链表的有效值：");
System.out.println(mylinkedList.getLength(mylinkedList.getHead()));
Heronode lastIndexNode=mylinkedList.findLastIndexNode(mylinkedList.getHead(),2);
System.out.println(lastIndexNode);
//腾讯面试题，把链表倒过来：123变成321
System.out.println("腾讯面试题，把链表倒过来：123变成321");
mylinkedList.reverseSetList(mylinkedList.getHead());
mylinkedList.list();
}
private static class HeroNode {
private int no;
private String name;
private String background;
private Heronode next;
//背景
public HeroNode(int no, String name, String background) {
this.no=no;
this.name=name;
this.background =background;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + ''' +
", background='" + background + ''' +
'}';
}
}
private static class MylinkedList {
//默认设置有一个头节点
private Heronode head=new HeroNode(0,"","");
public Heronode getHead() {
return head;
}
public void add(Heronode heroNode) {
Heronode temp=head;
//遍历出最后一个节点
while (true) {
if (temp.next==null) {
break;
}
//后移
temp=temp.next;
}
//对最后一个节点进行赋值
temp.next=heroNode;
}
public void list() {
//判断链表是否为空，如果是空的话，就没有必要遍历
if (head.next==null) {
System.out.println("链表为空");
return;
}
System.out.println("链表结果打印如下：");
//因为头节点不能动，所以我们需要一个辅助遍历来遍历
Heronode temp = head.next;
while (true) {
//判断是否为最后一个节点
if (temp==null) {
break;
}
//输出节点的信息
System.out.println(temp);
//将temp后移，一定要小心
temp=temp.next;
}
}
public void addByOrder(Heronode heroNode) {
//判断链表是否为空链表，如果是空链表的话，就直接加入
Heronode temp =head;
//链表不为空的情况
//遍历获取链表比heroNode.no大的值的前一个
while (true) {
//如果链表存在了，就不添加进去
if (temp.next==null) {
temp.next=heroNode;
break;
}else
if (temp.next.no==heroNode.no) {
System.out.println("链表已经存在了，无法在添加进去");
break;
}else
//下面是获取比heroNode.no大的值，然后temp就是前一个
if (temp.next.no>heroNode.no) {
//先让heroNode的next指向比它大值得那个
heroNode.next=temp.next;
//再让上一个指向添加的值
temp.next=heroNode;
break;
}else if (temp.next==null){
temp.next=heroNode;
break;
}
//如果不是的话，就后移，便于继续遍历
temp=temp.next;
}
}
public void addByOrder2(Heronode heroNode){
//因为头节点不能动，因此我们仍然通过一个辅助指针来帮助找到添加的位置
//要找到单链表的前一个，如果找到的是这个，那么久只能为这个赋值，
Heronode temp = this.head;
boolean flag=false;
while (true) {
if (temp.next==null) {//说明是链表的最后一个了，直接添加即可
break;
}
if (temp.next.no>heroNode.no) {
break;
}else if (temp.next.no==heroNode.no){//这个编号已经添加过了
flag=true;
break;
}
temp=temp.next;
}
//判断flag的值
if (flag) {
System.out.printf("准备插入的英雄编号 %d 已经存在了，不能加入n",heroNode.no);
}else {
//插入得到链表中，temp的后面
heroNode.next=temp.next;
temp.next=heroNode;
}
}
public void update(Heronode heroNodeNew) {
//判断链表是否为空
if (head.next==null) {
System.out.println("链表为空，无法进行修改，可以先添加");
return;
}
//设置一个标记，true表示存在这个编号，false表示不存在这个编号
boolean flag=false;
Heronode temp = head.next;
while (true) {
if (temp==null) {
//表示链表为空
System.out.println("链表已经遍历完了");
flag=false;
break;
}
//根据编号来确定是否有得修改
if (temp.no==heroNodeNew.no) {
flag=true;
break;
}
//后移
temp=temp.next;
}
if (flag==true) {
//如果是存在就进行修改
temp.name=heroNodeNew.name;
temp.background=heroNodeNew.background;
}else {
System.out.println("不存在此编号，所以无法修改");
}
}
public void delete(int no) {
//判断链表是否为空
if (head.next==null) {
System.out.println("链表为空，无法删除");
return;
}
Heronode temp = head.next;
boolean flag=false;//用于标记是否有得删除，有true，没有false
//链表不为空的话进行遍历，然后找到要删除的前一个节点
while (true) {
//判断链表是否为最后一个了，如果是的话，就break
if (temp==null) {
System.out.println("链表已经遍历完了，找不到，所以无法删除");
flag=false;
break;
}
if (temp.next.no==no) {
//表示找到了，直接标记为找到
flag=true;
break;
}
//没有找到，就后移
temp=temp.next;
}
if (flag==true) {
temp.next=temp.next.next;
}else {
System.out.println("不存在要删除的链表节点");
}
}
public int getLength(Heronode head) {
//判断链表是否为空，如果为空的话，就有效值就为0
if (head.next==null) {
return 0;
}
//链表不为空
//标记一个值，来统计，每次可以遍历一个就加1。默认为0
int size=0;
Heronode cur = head.next;
while (cur != null) {
size++;
//后移
cur=cur.next;
}
return size;
}
public Heronode findLastIndexNode(Heronode head, int lastIndex) {
Heronode temp = head.next;
//链表为空，无法找
if (temp==null) {
System.out.println("链表为空，无法查找");
return null;
}
//链表不为空
int size=getLength(head);//链表的长度
//查找的索引值不合理（小于0，获取大于链表的长度）
if (lastIndex<=0||lastIndex>size) {
System.out.println("查找的倒数索引不合理");
return null;
}
Heronode findNode=null;
for (int i = 0; i < size-lastIndex; i++) {
findNode=temp.next;
temp=temp.next;
}
return findNode;
}
public void reverseSetList(Heronode head) {
//判断链表是否可以反向，或没必要反向：null，或者链表长度为1，那么没有必要反向
if (head.next==null||head.next.next==null) {
System.out.println("链表长度为null或者长度为1，没有必要反向");
return;
}
//长度可以反向
//用来反向的辅助头节点
Heronode reverseHead=new HeroNode(0,"","");
//当前节点
Heronode cur = head.next;
//当前节点的下一个节点，为了不断链
Heronode curNext = null;
//遍历队列
while (cur != null) {
curNext=cur.next;//为当前节点的下一个节点赋值，目的是保证链表不断裂
cur.next=reverseHead.next;//当前节点的下一个指向赋值头节点的下一个
reverseHead.next=cur;//为辅助节点的下一个赋值
cur=curNext;//当前节点后移
}
head.next=reverseHead.next;//最后头节点指向反向节点的next
}
}
}
2.讲解
1.
2.
3.反思总结
1.curNext来保证链表不断。因为head的那个已经断了，所以后移要cur=curNext
