リンクリスト（Java）のMerge Sortで予期しない結果が発生しました

Question

class Node { 

    int data; 
    Node next; 

    public Node(int a) {data = a; next = null;} 
} 

public class List { 

    public Node head; 

    public List() { 
     head = null; 
    } 

    public boolean isEmpty() { 
     return head == null; 
    } 

    public void insertAtFront(int a) { 
     Node node = new Node(a); 
     node.next = head; 
     head = node; 
    } 

    public void insertAtEnd(int a) { 
     Node node = new Node(a); 
     // this check cannot be omitted 
     // otherwise you get NullPointerException on an empty list. 
     if (head == null) { 
      insertAtFront(a); 
      return; 
     } 
     Node cur = head; 
     while(cur.next != null) { 
      cur = cur.next; 
     } 
     cur.next = node; 
    } 

    public void insertAfter(Node node, int a) { 
     Node newNode = new Node(a); 
     if (node == null) { 
      System.out.println("Oops..."); 
      return; 
     } 
     newNode.next = node.next; 
     node.next = newNode; 
    } 

    public Node search(int a) { 
     Node cur = head; 
     while(cur != null && cur.data != a) cur = cur.next; 
     return cur; 
    } 

    public int deleteFirst() { 
     if (head == null) { 
      System.out.println("Oops..."); 
      return -1; 
     } 
     Node node = head; 
     head = head.next; 
     node.next = null; 
     return node.data; 
    } 

    public int deleteLast() { 
     if (head == null || head.next == null) 
      return deleteFirst(); 
     Node second = head; 
     Node cur = second.next; 
     // when the thile loop finishes, 
     // cur points to the last node. 
     while(cur.next != null) { 
      second = cur; 
      cur = cur.next; 
     } 
     second.next = null; 
     return cur.data; 
    } 

    public String toString() { 
     StringBuilder sb = new StringBuilder(); 
     Node cur = head; 
     while(cur != null) { 
      sb.append(cur.data); 
      if (cur.next != null) sb.append(", "); 
      cur = cur.next; 
     } 
     return sb.toString(); 
    } 

    private Node merge(Node head1, Node head2) { 
     Node dummy = new Node(0); 
     Node tail = dummy; 
     while (head1 != null && head2 != null) { 
      if (head1.data < head2.data) { 
       tail.next = head1; 
       head1 = head1.next; 
      } else { 
       tail.next = head2; 
       head2 = head2.next; 
      } 
      tail = tail.next; 
     } 
     if (head1 != null) { 
      tail.next = head1; 
     } else { 
      tail.next = head2; 
     } 

     return dummy.next; 
    } 

    public Node mergesort(Node head) { 
     if (head == null || head.next == null) { 
      return head; 
     } 

     Node mid = findMiddle(head); 
     Node right = mergesort(mid.next); 
     mid.next = null; 
     Node left = mergesort(head); 

     return merge(left, right); 
    } 

    private Node findMiddle(Node head) { 
     Node slow = head, fast = head.next; 
     while (fast != null && fast.next != null) { 
      fast = fast.next.next; 
      slow = slow.next; 
     } 
     return slow; 
    } 

    public static void main(String[] args) { 
     List list = new List(); 
     list.insertAtFront(37); 
     list.insertAtFront(99); 
     list.insertAtFront(12); 
     // the list at page 88 of the slides. 
     System.out.println(list); 
     list.insertAtFront(75); 
     System.out.println(list); 
     list.insertAtEnd(38); 
     System.out.println(list); 
     list.insertAfter(list.search(12), 85); 
     System.out.println(list); 
     list.mergesort(list.head); 
     System.out.println("after sorting: " + list + "\n"); 
     System.out.println("delete the first, which is " + list.deleteFirst()); 
     System.out.println(list); 
     System.out.println("delete the last, which is " + list.deleteLast()); 
     System.out.println(list); 
    } 
} 

ここはマージソートのリンクリストのコードです。ただし、リンクされたリストの後部のみが表示されました。何が問題ですか....？

12、99、37

75、12、99、37

75、12、99、37、38

75、12、85、：のIntelliJを使用

99、37、38

ソート後：75、85、99

75である、第一の削除 、99

は、あなたがそこにリストの先頭を変更していない主な方法でマージソート（）からの復帰を取得しながら、99

Answer 1

である、最後に削除します。 は、だからあなたの場合にはリストがソートされているが、ヘッドは、メインメソッドのコード

によると75だけとの事な作業を右に残って 置き換えますlist.mergesort（list.head）。 with：list.head = list.mergesort（list.head）;

Answer 2

コードをリファクタリングしました。以下を参照してください。うまくいけばそれはかなり自明です。

public class List { 

    public Node head; 

    public List() { 
     head = null; 
    } 

    public boolean isEmpty() { 
     return head == null; 
    } 

    public void insertAtFront(int a) { 
     Node node = new Node(a); 
     node.next = head; 
     head = node; 
    } 

    public void insertAtEnd(int a) { 
     Node node = new Node(a); 
     if (head == null) { 
      head = node; 
     } 
     else { 
      Node cur = head; 
      while(cur.next != null) { 
       cur = cur.next; 
      } 
      cur.next = node; 
     } 
    } 

    public void insertAfter(Node predecessor, int a) { 
     if (predecessor == null) { 
      throw new IllegalArgumentException("Predecessor cannot be null"); 
     } 
     Node node = new Node(a); 
     node.next = predecessor.next; 
     predecessor.next = node; 
    } 

    /** returns null if a is not found */ 
    public Node findFirst(int a) { 
     Node cur = head; 
     while(cur != null && cur.data != a) { 
      cur = cur.next; 
     } 
     return cur; 
    } 

    public int removeFirst() { 
     if (head == null) {    
      throw new IllegalArgumentException("Cannot remove from empty list"); 
     } 
     Node node = head; 
     head = head.next; 
     node.next = null; 
     return node.data; 
    } 

    public int removeLast() { 
     if (head == null || head.next == null) { 
      return removeFirst(); 
     } 
     Node cur = head; 
     while(cur.next.next != null) { 
      cur = cur.next; 
     } 
     int data = cur.next.data; 
     cur.next = null; 
     return data; 
    } 

    public String toString() { 
     StringBuilder sb = new StringBuilder(); 
     sb.append("["); 
     Node cur = head; 
     while(cur != null) { 
      sb.append(cur.data); 
      if (cur.next != null) { 
       sb.append(", "); 
      } 
      cur = cur.next; 
     } 
     sb.append("]"); 
     return sb.toString(); 
    } 

    private Node merge(Node head1, Node head2) { 
     Node dummy = new Node(0); 
     Node tail = dummy; 
     while (head1 != null && head2 != null) { 
      if (head1.data < head2.data) { 
       tail.next = head1; 
       head1 = head1.next; 
      } else { 
       tail.next = head2; 
       head2 = head2.next; 
      } 
      tail = tail.next; 
     } 
     if (head1 != null) { 
      tail.next = head1; 
     } else { 
      tail.next = head2; 
     } 
     return dummy.next; 
    } 

    public Node mergesort(Node head) { 
     if (head == null || head.next == null) { 
      return head; 
     } 
     Node mid = findMiddle(head); 
     Node right = mergesort(mid.next); 
     mid.next = null; 
     Node left = mergesort(head); 
     return merge(left, right); 
    } 

    private Node findMiddle(Node head) { 
     Node slow = head, fast = head.next; 
     while (fast != null && fast.next != null) { 
      fast = fast.next.next; 
      slow = slow.next; 
     } 
     return slow; 
    } 

    public static void main(String[] args) { 
     List list = new List(); 
     list.insertAtFront(37); 
     list.insertAtFront(99); 
     list.insertAtFront(12); 

     // the list at page 88 of the slides. 
     System.out.println(list); 

     list.insertAtFront(75); 
     System.out.println(list); 

     list.insertAtEnd(38); 
     System.out.println(list); 

     list.insertAfter(list.search(12), 85); 
     System.out.println(list); 

     list.head = list.mergesort(list.head); 
     System.out.println("after sorting: " + list + "\n"); 

     System.out.println("delete the first, which is " + list.deleteFirst()); 
     System.out.println(list); 

     System.out.println("delete the last, which is " + list.deleteLast()); 
     System.out.println(list); 
    } 
} 

実際のデータとして負の数を防止していないため、削除が失敗した場合は-1を返すことは悪い考えです。