合并两个链表并降序排列时数字排序错误问题求助

问题详情 #

• 需求：实现用户输入两个整数链表，合并后生成降序排列的新链表。
• 错误现象：两位数（如10）被当作字符串比较，导致排序逻辑出错。
  • 输入示例：
    • 第一个链表输入：1 8 0 4
    • 第二个链表输入：3 2 9 10
  • 当前错误输出：9 8 4 3 2 10 1 0
  • 期望输出：10 9 8 4 3 2 1 0
• 尝试情况：曾试图将数据类型从String改为int，但出现大量编译错误，现有代码如下：

现有主类代码 #

package homework;

import static homework.Cipher.decode;
import static homework.Cipher.encode;
import java.util.Scanner;

public class HOMEWORK {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int x = 0;
        while (x != 5) {
            System.out.println("-_-_-_-_-MENU-_-_-_-_-
1-Encrypt Text"
                    + "\n2-Decrypt Text"
                    + "\n3-Merge two sorted list in decreasing order"
                    + "\n4- Reverse Linked List Recursively "
                    + "\n5- Exit ");
            System.out.println("Please enter your choice: ");
            x = input.nextInt();
            input.nextLine();
            switch (x) {
                case 1:
                    System.out.println("Please enter Line to encode: ");
                    String plaintext = input.nextLine();
                    System.out.println("Please enter Shift  Number:");
                    int number = input.nextInt();
                    input.nextLine();

                    String encoded = encode(plaintext, number);
                    System.out.println("Result:");
                    System.out.println(encoded);
                    break;
                case 2:
                    System.out.println("Please enter Line to decode: ");
                    String code = input.nextLine();
                    System.out.println("Please enter Shift  Number:");
                    int number1 = input.nextInt();
                    input.nextLine();

                    System.out.println("Result:");
                    System.out.println(decode(code, number1));
                    break;
                case 3:
                    Merge list1 = new Merge();
                    Merge list2 = new Merge();
                    System.out.println("Enter first scentence :");
                    String[] string1 = input.nextLine().split(" ");

                    System.out.println("Enter second scentence :");
                    String[] string2 = input.nextLine().split(" ");
                    for (int i = 0; i < string1.length; i++) {
                        list1.insert(string1[i]);
                    }
                    for (int i = 0; i < string2.length; i++) {
                        list2.insert(string2[i]);
                    }
                    Merge merged = list1.merge(list1, list2);

                    System.out.println("Result ");
                    merged.Display();
                    System.out.println();
                    break;
                case 4:
                    SinglyLinkedList LL = new SinglyLinkedList();
                    System.out.println("Enter  scentence to reverse :");
                    String[] string = input.nextLine().split(" ");
                    for (int i = 0; i < string.length; i++) {
                        LL.addLast(string[i]);
                    }
                    System.out.println("REVERSED");
                    System.out.println(LL.reverse());
                    break;
                case 5:
                default:
                    System.out.println(" Goodbye ");
            }
        }
    }
}

现有Merge类代码 #

package homework;

public class Merge {
    public Node head = null; // head node of the list (or null if empty) 
    // access methods 
    int size = 0;

// update methods 
    public void addFirst(String e) { // adds data e to the front of the list 
        head = new Node(e, head);// create and link a new node 
        size++;
    }

    public String deleteFirst() {
        if (size == 0) {
            return "";
        }
        String remo = head.element;
        head = head.next;
        size--;
        return remo;
    }

    public void insert(String element) {
        if (head == null || head.element.compareTo(element) >= 0) {
            addFirst(element);
        } else {
            Node p = head;
            Node c = p.next;
            while (c != null && c.element.compareTo(element) <= 0) {
                p = c;
                c = c.next;
            }
            Node newest = new Node(element, c); // node will eventually be the tail 
            p.next = newest;
        }
    }

    public void Display() {
        Node N = head;
        while (N != null) {
            System.out.print(N.element + " ");
            N = N.next;
        }
    }

    public Merge merge(Merge list1, Merge list2) {
        Merge merged = new Merge();
        Node head1 = list1.head;
        Node head2 = list2.head;
        if (head1 == null) {
            return list2;
        }
        if (head2 == null) {
            return list1;
        }
        merged.head = null;
        if (head1.element.compareTo(head2.element) <= 0) {
            merged.head = head1;
            head1 = head1.next;
        } else {
            merged.head = head2;
            head2 = head2.next;
        }
        Node mergedTail = merged.head;
        while (head1 != null && head2 != null) {
            Node temp = null;
            if (head1.element.compareTo(head2.element) <= 0) {
                temp = head1;
                head1 = head1.next;
            } else {
                temp = head2;
                head2 = head2.next;
            }
            mergedTail.next = temp;
            mergedTail = temp;
        }
        if (head1 != null) {
            mergedTail.next = head1;
        } else if (head2 != null) {
            mergedTail.next = head2;
        }
        Node p = null;
        Node c = merged.head;
        Node next = null;
        while (c != null) {
            next = c.next;
            c.next = p;
            p = c;
            c = next;
        }
        merged.head = p;
        return merged;
    }

    public static class Node {
        private String element;
        private Node next;

// reference to the data stored at this node // reference to the subsequent node in the list
        public Node(String e, Node n) {
            element = e;
            next = n;
        }
    }
}

修复方案：将链表存储类型改为int #

核心是把所有字符串相关的操作替换为整数操作，具体修改如下：

1. 修改Merge类的Node结构 #

把Node中的String element改为int，并更新构造方法：

public static class Node {
    private int element;
    private Node next;

    public Node(int e, Node n) {
        element = e;
        next = n;
    }
}

2. 更新Merge类中的所有方法 #

package homework;

public class Merge {
    public Node head = null;
    int size = 0;

    // 修改addFirst参数为int
    public void addFirst(int e) {
        head = new Node(e, head);
        size++;
    }

    // 修改deleteFirst返回值为Integer，空列表返回null
    public Integer deleteFirst() {
        if (size == 0) {
            return null;
        }
        int remo = head.element;
        head = head.next;
        size--;
        return remo;
    }

    // 修改insert方法，用整数比较替代字符串比较
    public void insert(int element) {
        if (head == null || head.element >= element) {
            addFirst(element);
        } else {
            Node p = head;
            Node c = p.next;
            while (c != null && c.element <= element) {
                p = c;
                c = c.next;
            }
            Node newest = new Node(element, c);
            p.next = newest;
        }
    }

    public void Display() {
        Node N = head;
        while (N != null) {
            System.out.print(N.element + " ");
            N = N.next;
        }
    }

    // 修改merge方法中的比较逻辑为整数比较
    public Merge merge(Merge list1, Merge list2) {
        Merge merged = new Merge();
        Node head1 = list1.head;
        Node head2 = list2.head;
        if (head1 == null) {
            return list2;
        }
        if (head2 == null) {
            return list1;
        }
        merged.head = null;
        if (head1.element <= head2.element) {
            merged.head = head1;
            head1 = head1.next;
        } else {
            merged.head = head2;
            head2 = head2.next;
        }
        Node mergedTail = merged.head;
        while (head1 != null && head2 != null) {
            Node temp = null;
            if (head1.element <= head2.element) {
                temp = head1;
                head1 = head1.next;
            } else {
                temp = head2;
                head2 = head2.next;
            }
            mergedTail.next = temp;
            mergedTail = temp;
        }
        if (head1 != null) {
            mergedTail.next = head1;
        } else if (head2 != null) {
            mergedTail.next = head2;
        }
        // 反转链表得到降序
        Node p = null;
        Node c = merged.head;
        Node next = null;
        while (c != null) {
            next = c.next;
            c.next = p;
            p = c;
            c = next;
        }
        merged.head = p;
        return merged;
    }
}

3. 修改主类中case3的插入逻辑 #

把输入的字符串转为整数后再插入：

case 3:
    Merge list1 = new Merge();
    Merge list2 = new Merge();
    System.out.println("Enter first list (integers separated by space):");
    String[] string1 = input.nextLine().split(" ");

    System.out.println("Enter second list (integers separated by space):");
    String[] string2 = input.nextLine().split(" ");
    // 转为int后插入
    for (int i = 0; i < string1.length; i++) {
        list1.insert(Integer.parseInt(string1[i]));
    }
    for (int i = 0; i < string2.length; i++) {
        list2.insert(Integer.parseInt(string2[i]));
    }
    Merge merged = list1.merge(list1, list2);

    System.out.println("Result ");
    merged.Display();
    System.out.println();
    break;

内容的提问来源于stack exchange，提问作者Maram uwu