java按排名插入单链表问题

Question

package com.atzy.LinkedList;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //测试
        PersonNode person1 = new PersonNode(1,"小明",10);
        PersonNode person2 = new PersonNode(3,"小花",12);
        PersonNode person3 = new PersonNode(2,"小红",10);
        SingleLinkedList list1 = new SingleLinkedList();
        list1.AddPerson(person1);
        list1.AddPerson(person2);
        list1.Insert(person3);
        list1.ShowList();
        
    }

}

class SingleLinkedList{
    //头节点
    private PersonNode headNode = new PersonNode(0, "", 0);//为什么要用private？
    //添加节点到单链表中1.不按照排名，直接加在链表末尾
    public void AddPerson(PersonNode personNode){
        PersonNode temp = headNode;//头节点不能动，所以定义一个temp遍历单链表
        while(true) {
            if(temp.next == null) {
                temp.next = personNode;
                break;
            }
            temp = temp.next;
        }
    }
    //2.按照排名插入数据
    public void Insert(PersonNode personNode) {
        PersonNode temp = headNode;
        while(true) {
            if(temp.next == null) {
                break;
            }
            if(temp.num == personNode.num) {
                System.out.println("该排名已存在");
                break;
            }
            if(temp.num > personNode.num) {
                personNode.next = temp.next;
                temp.next = personNode;
            }
            temp = temp.next;
        }
        
    }
    public void ShowList(){
        if(headNode.next == null) {
            System.out.println("链表为空");
        }
        PersonNode temp = headNode.next;
        while(true) {
            if(temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
    
}


class PersonNode{
    public int num;
    public String name;
    public int age;
    public PersonNode next;
    
    //创建构造器——单链表
    public PersonNode(int pNum,String pName,int pAge){
        this.num = pNum;
        this.name = pName;
        this.age = pAge;
        
    }

    @Override
    public String toString() {
        return "PersonNode [num=" + num + ", name=" + name + ", age=" + age + "]";
    }
    
    
    
}

请问一下为什么输出结果不是小明、小红、小花呀？谢谢~

Answer 1

引自免费微信小程序：皆我百晓生

在你提供的Java代码中，存在一个逻辑错误导致链表插入节点后并没有按照排名顺序排列。问题在于Insert方法中的条件判断和插入逻辑。

当需要将新节点按排名插入时，正确的逻辑应该是：

public void Insert(PersonNode personNode) {
    PersonNode pre = headNode; // 需要一个前置节点来保存当前节点的前一个节点
    PersonNode temp = headNode.next; // 从头节点的下一个节点开始遍历

    while (temp != null) {
        if (temp.num > personNode.num) { // 找到排名大于新节点的位置
            personNode.next = temp; // 新节点指向原位置的节点
            pre.next = personNode; // 前置节点（找到的位置前一个节点）指向新节点
            break;
        }
        pre = temp; // 移动前置节点到下一个节点
        temp = temp.next;
    }

    // 如果链表为空或者新节点的排名最小，则直接添加到链表头部
    if (temp == null || pre == headNode && pre.num >= personNode.num) {
        personNode.next = headNode.next;
        headNode.next = personNode;
    }
}

这样修改后的Insert方法可以正确地将新节点person3按照排名插入到已存在的链表中。现在运行程序，输出结果将会是按照排名排序的小明、小红、小花。