插入排序整数从文件读取到链表java

Question

我需要将文件中的整数读入链表，使用插入排序对列表进行排序，然后使用 java 报告我的机器完成插入排序所用的时间。目前，我的代码做的一切都是正确的，除了从文件中读取，它只读取第一个和最后一个数字。例如，如果我以相反的顺序读取数字 1 到 5000 的文件，它只会读取和排序 5000 和 1。

如何将文件中的所有整数读入 ListNodes？代码贴在下面：

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class InsertionLinkedList {

    public static ListNode insertionSortList(ListNode head) {

        long start = System.nanoTime();
        if (head == null || head.next == null)
            return head;

        ListNode newHead = new ListNode(head.val);
        ListNode pointer = head.next;

        // loop through each element in the list
        while (pointer != null) {
            // insert this element to the new list

            ListNode innerPointer = newHead;
            ListNode next = pointer.next;

            if (pointer.val <= newHead.val) {
                ListNode oldHead = newHead;
                newHead = pointer;
                newHead.next = oldHead;
            } else {
                while (innerPointer.next != null) {

                    if (pointer.val > innerPointer.val && pointer.val <= innerPointer.next.val) {
                        ListNode oldNext = innerPointer.next;
                        innerPointer.next = pointer;
                        pointer.next = oldNext;
                    }

                    innerPointer = innerPointer.next;
                }

                if (innerPointer.next == null && pointer.val > innerPointer.val) {
                    innerPointer.next = pointer;
                    pointer.next = null;
                }
            }

            // finally
            pointer = next;
        }
        long time = System.nanoTime() - start;
        System.out.printf("The time taken was %.1f ns%n", (double) time);
        return newHead;
    }

    public static void main(String[] args) throws FileNotFoundException {

        Scanner scanner = new Scanner(new File("random5k.txt"));
        ListNode insertion = new ListNode(scanner.nextInt());
        while(scanner.hasNextInt()){
            ListNode nextNode = new ListNode(scanner.nextInt());
            insertion.next = nextNode;
        }

        insertion = insertionSortList(insertion);
    }
}

Answer 1

Currently, my code does everything right except for reading from the file, it only reads in the first and last number. For example, if I read from a file that has the numbers 1 to 5000 in reverse order it will only read and sort 5000 and one.

您实际上正确地读取了文件中的所有数字。只是当您尝试填充 ListNode 对象 insertion 时，您没有将每个节点的 next 指向实际的下一个节点。在您的程序中查看我的编辑。

public static void main(String[] args) throws FileNotFoundException {

Scanner scanner = new Scanner(new File("random5k.txt"));
ListNode insertion = new ListNode(scanner.nextInt());
ListNode intNodes = insertion;
while(scanner.hasNextInt()){
    ListNode nextNode = new ListNode(scanner.nextInt());
    insertion.next = nextNode;
    insertion = nextNode;
}
intNodes = insertionSortList(intNodes);
}

插入排序整数从文件读取到链表java

Insertion sorting integers read from a file into a linked list java

java

file

sorting

integer

insertion-sort