Linked List Exercise 2024-04-03

Main.java

// 编写一个程序，维护一个有序链表。允许用户输入任意数量的想输入的整数，并将其插入链表，在插入的同时维持链表元素从小到大的排序。

package org.qianq;

import java.util.Scanner;

class Node {
    int data;
    Node next;
}

class LinkedList {
    Node head = null;

    public void traverse() {
        Node current = head;
        while (current.next != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.print(current.data + " ");
        System.out.println();
    }

    /**
     * 在插入新数据时，保持链表有序（从小到大）
     * @param newData 新数据
     */
    public void sortedInsertion(int newData) {
        Node newNode = new Node();  // 创建新节点
        newNode.data = newData;     // 设置新节点的数据
        newNode.next = null;        // 将新节点的“下一个”指针指向默认的 null
        if (head == null) {
            // 如果 head 指针是 null，说明链表为空
            // 直接将新节点设置为 head
            head = newNode;
        } else if (head.data >= newData) {
            // 如果 head 指针的数据大于等于新数据，则意味着新数据应该插入到 head 之前
            // 将新节点的“下一个”指针指向 head，然后将 head 指针指向新节点
            newNode.next = head;
            head = newNode;
        } else {
            // 否则，遍历链表，找到合适的位置插入新节点
            Node current = head;
            while (current.next != null) {
                if (current.data < newData && current.next.data >= newData) {
                    // 如果当前节点的数据小于新数据，且下一个节点的数据大于等于新数据，则认为新数据应该插入到当前节点之后
                    newNode.next = current.next;    // 将新节点的“下一个”指针指向当前节点的下一个节点
                    current.next = newNode;         // 将当前节点的“下一个”指针指向新节点
                    return;                         // 插入完成，直接返回
                } else {
                    current = current.next;         // 否则，没有找到合适的位置，继续遍历
                }
            }
            if (current.data < newData) {           // 如果遍历到链表的末尾，且当前节点的数据小于新数据，则将新节点插入到链表的末尾
                current.next = newNode;             // 将当前节点（目前链表的最后一个节点）的“下一个”指针指向新节点
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        String input;

        LinkedList linkedList = new LinkedList();

        while (true) {
            System.out.print("Enter a number or Q to quit: ");
            input = console.nextLine();
            if (input.equalsIgnoreCase("Q")) {
                break;
            }
            linkedList.sortedInsertion(Integer.parseInt(input));
        }

        linkedList.traverse();
    }
}