两条单链表分别插入同一个节点，分别打印两链表中的元素，发现和预期不一样。我的代码如下：
1 HeroNode h1=new HeroNode(1,"宋江","及时雨"); 2 HeroNode h2=new HeroNode(2,"卢俊义","玉麒麟"); 3 HeroNode h3=new HeroNode(3,"吴用","智多星"); 4 HeroNode h4=new HeroNode(4,"林冲","豹子头"); 5 6 //创建链表 7 SingleLinkedList sll1=new SingleLinkedList(); 8 SingleLinkedList sll2=new SingleLinkedList(); 9 10 //按编号顺序插入h1和h4 11 sll1.addByOrder(h1); 12 sll1.addByOrder(h4); 13 14 sll2.addByOrder(h1);
结果如下：
我改一下代码，sll2不添加h1了，添加h2，h3：
1 HeroNode h1=new HeroNode(1,"宋江","及时雨"); 2 HeroNode h2=new HeroNode(2,"卢俊义","玉麒麟"); 3 HeroNode h3=new HeroNode(3,"吴用","智多星"); 4 HeroNode h4=new HeroNode(4,"林冲","豹子头"); 5 6 //创建链表 7 SingleLinkedList sll1=new SingleLinkedList(); 8 SingleLinkedList sll2=new SingleLinkedList(); 9 10 sll1.addByOrder(h1); 11 sll1.addByOrder(h4); 12 13 //sll2.addByOrder(h1); 14 sll2.addByOrder(h2); 15 sll2.addByOrder(h3);
结果又变正常了！
HeroNode代码如下：
1 class HeroNode {
2 public int no;
3 public String name;
4 public String nickName;
5 public HeroNode next;
6
7 public HeroNode(int no,String name,String nickName){
8 this.no=no;
9 this.name=name;
10 this.nickName=nickName;
11 }
12
13 @Override
14 public String toString() {
15 return "HeroNode{" +
16 "no=" + no +
17 ", name='" + name + '\'' +
18 ", nickName='" + nickName + '\'' +
19 '}';
20 }
21 }
View Code
SingleLinkedList代码如下：
class SingleLinkedList {
public HeroNode head=new HeroNode(0,null,null);
//添加结点
public void addElement(HeroNode hero){
//使用辅助变量来遍历链表
HeroNode temp=head;
while(temp.next!=null){
temp=temp.next;
}
temp.next=hero;
}
//按英雄顺序添加结点，如果已经有了，则添加失败
public void addByOrder(HeroNode hero){
//因为头节点不能动，所以我们通过辅助变量来帮助找到添加的位置
HeroNode temp=head;
boolean flag=false;
while(true){
if(temp.next==null){ //遍历完整个链表，插入节点应该是最后一个节点
break;
}
if(temp.next.no>hero.no){ //找到添加位置，在temp后，temp.next前
break;
}else if(temp.next.no== hero.no){ //已有此节点
flag=true;
break;
}
temp=temp.next;
}
if(flag){
System.out.printf("已有编号为%d的节点，无法添加!\n",hero.no);
}else {
hero.next=temp.next;
temp.next=hero;
}
}
//修改结点，如果没找到，则修改失败
public void update(HeroNode hero){
HeroNode temp=head;
boolean flag=true; //true代表需要修改
while(true){
if(temp.next==null){
flag=false;
break;
}
if(temp.next.no==hero.no){ //temp.next为修改的位置
break;
}
temp=temp.next;
}
if(flag){
temp.next.name=hero.name;
temp.next.nickName=hero.nickName;
}else {
System.out.printf("没有找到编号为%d的节点，无法修改！\n",hero.no);
}
}
//删除节点，如果没找到，则删除失败
public void delete(int no){
HeroNode temp=head;
boolean flag=true; //true代表可以删除
while(true){
if (temp.next==null){ //没有找到要删除的节点
flag=false;
break;
}
if(temp.next.no==no){ //删除的节点为temp.next
break;
}
temp=temp.next;
}
if(flag){
temp.next=temp.next.next;
}else {
System.out.printf("没有找到编号为%d的节点，无法删除！\n",no);
}
}
//输出链表
public void list(){
if(head.next==null){
System.out.println("链表为空！");
}
HeroNode temp=head.next;
while(temp!=null){
System.out.println(temp);
temp=temp.next;
}
}
//获取单链表有效节点个数
public int length(){
int count=0;
HeroNode temp=head;
while(temp.next!=null){
temp=temp.next;
count++;
}
return count;
}
//查找倒数第k个节点：先遍历一次，求出链表长度，再遍历(length()-k+1)次得到该节点
public HeroNode findTheLastK(int k){
HeroNode temp=head;
if(length()==0){
throw new RuntimeException("链表为空，查找异常！");
}
if(k>length()){
throw new RuntimeException("查找倒数第"+k+"个节点异常：查找节点编号超出链表长度！");
}
for(int i=0;i<(length()-k+1);i++){
temp=temp.next;
}
return temp;
}
//反转单链表：遍历原链表，把每一个节点都头插到新链表上，再把head.next指向新链表的第一个元素节点
public void reverse(){
//如果为空或只有一个，不需要反转
if(head.next==null || head.next.next==null){
return;
}
HeroNode temp=head.next;
HeroNode reverseHead=new HeroNode(0,null,null);
HeroNode node=null;
while(temp!=null){
//用node暂存temp.next
node=temp.next;
//把temp头插到reverseHead
temp.next=reverseHead.next;
reverseHead.next=temp;
//移动指针
temp=node;
}
head.next=reverseHead.next;
}
//逆序打印：（不建议先反转再打印，会改变原来的链表）遍历链表，把每个节点压入栈中，出栈打印，链表结构不改变
public void reversePrint(){
if(head.next==null){
System.out.println("链表为空，无法逆序打印！");
return;
}
HeroNode temp=head.next;
HeroNode node=null;
Stack<HeroNode> stack=new Stack<>();
while(temp!=null){
//保存temp.next，以免链表丢失
node=temp.next;
//压入栈中
stack.push(temp);
temp=temp.next;
}
while(!stack.isEmpty()){
System.out.println(stack.pop());
}
}
//有序合并两个单链表
public void combineList(SingleLinkedList linkedList){
HeroNode anotherHead=linkedList.head;
if(anotherHead.next==null){
return;
}
HeroNode temp=anotherHead.next;
HeroNode node=null;
while(temp!=null){
//保存temp2.next，以免丢失链表
node=temp.next;
//按顺序插入
addByOrder(temp);
temp=node;
}
}
}
View Code
为什么会出现这个结果呢？
在sll1中插入h1、h4之后，此时sll1链表：head-->h1-->h4-->null。h1的next指向h4！
在sll2添加h1的时候，实际上并不止是添加h1，而是添加h1-->h4-->null这条链！
SingleLinkedList里的addByOrder()执行后，sll2：head-->h1-->null，而sll1的head指向h1，sll1也会变成：head-->h1-->null！
如果单链表里面的元素，不是引用类型，而是基本数据类型呢？是否会出现这种情况呢？答案是不会！