java - 用链表实现归并排序

Question

我正在尝试在网上找到的一个问题，即使用链表实现合并排序，但是使用我学校教授的奇怪的列表接口实现而不是仅使用节点，因此从其他解决方案中简单复制在这里不起作用。我通常只是在扩展，BasicLinkedList并没有真正打扰界面。这是我的驱动程序代码和类，合并排序并没有按照我想要的方式运行，调试了很长时间后我似乎无法弄清楚为什么。有谁可以帮我离开这里吗？

如果您需要更多信息，请通知我。

import java.util.*;

class Main {
    public static void main(String [] args) {
        BasicLinkedList<Integer> lst = BasicLinkedList.of(4,2,1,3);
        BasicLinkedList<Integer> sortedList = BasicLinkedList.mergeSort(lst);
        sortedList.print();

    }
}


class ListNode <E> {
    protected E element;
    protected ListNode <E> next;

    /* constructors */
    public ListNode (E item) { 
        element = item; 
        next = null; 
    }

    public ListNode (E item, ListNode <E> n) { 
        element = item; 
        next=n;
    }

    /* get the next ListNode */
    public ListNode <E> getNext ( ) {
        return this.next;
    }

    /* get the element of the ListNode */
    public E getElement ( ) {
        return this.element;
    }

    public void setNext(ListNode<E> item) {
        this.next = item;
    }


}




class BasicLinkedList <E> implements LinkedListInterface <E> {
    protected ListNode <E> head = null;
    protected int num_nodes = 0;


    public boolean isEmpty() 
        { return (num_nodes == 0); }

    public int size( ) 
        { return num_nodes; }

    public E getFirst ( ) throws NoSuchElementException {
        if (head == null) 
            throw new NoSuchElementException("can't get from an empty list");
        else return head.element;
    }

    public boolean contains (E item) {
        for (ListNode <E> n = head; n!= null; n=n.next)
            if (n.getElement().equals(item)) return true;

        return false;
    }

    public void addFirst (E item) {
        head = new ListNode <E> (item, head);
        num_nodes ++;
    }

    public E removeFirst ( ) throws NoSuchElementException {
        ListNode <E> ln;
        if (head == null) 
            throw new NoSuchElementException ("can't remove from an empty list");
        else { 
            ln = head;
            head = head.next;
            num_nodes --;
            return ln.element;
        }
    }

    public void print2 ( ) throws NoSuchElementException {
        if (head == null)
            throw new NoSuchElementException ("Nothing to print...");

        ListNode <E> ln = head;
        System.out.print ("List is: " + ln.element);
        for (int i=1; i < num_nodes; i++) {
            ln = ln.next;
            System.out.print (", " + ln.element );
        }
        System.out.println(".");
    }

    public void print () throws NoSuchElementException {
        if (head == null)
            throw new NoSuchElementException ("Nothing to print...");

        Iterator <E> itr = iterator();
        System.out.print ("List is: " + itr.next() );
        while (itr.hasNext()) 
            System.out.print ( ", " + itr.next() );
        System.out.println(".");
    }

    public Iterator<E> iterator() { 
        return new LinkedListIterator(); 
    }

    private class LinkedListIterator implements Iterator<E> {
        private ListNode<E> current = head;

        public boolean hasNext(){ return current != null;}
        public void remove()    { throw new UnsupportedOperationException(); }
        public E next() {
            if ( !hasNext()) {
                throw new NoSuchElementException();
            }
            E element = current.element;
            current = current.next;
            return element;
        }
    }


    public static <E> BasicLinkedList<E> of(E ... values) {
        BasicLinkedList<E> lst = new BasicLinkedList<>();
        for (int i=values.length-1;i> -1; i--) {
            lst.addFirst(values[i]);
        }
        return lst;
    }

    public static BasicLinkedList<Integer> mergeSort(BasicLinkedList<Integer> original) {
        if (original.size() < 2) {
            return original;
        } else {
            int totalSize = original.size();
            int newSize = totalSize/2;

            ListNode<Integer> middle = getMiddle(original);
            ListNode<Integer> nextOfMiddle = middle.next; 
            BasicLinkedList<Integer> right = new BasicLinkedList<>();
            right.head = nextOfMiddle;
            right.num_nodes = totalSize- newSize;
            //Create the left list, firstly by creating an empty shell and replace the head node
            BasicLinkedList<Integer> left = new BasicLinkedList();
            left.head = original.head;
            right.num_nodes = newSize;




            // set the next of middle node to null 
            middle.setNext(null);
            // System.out.println("Before MS");
            // debug(left,right);


            BasicLinkedList<Integer> newLeft = mergeSort(left);
            BasicLinkedList<Integer> newRight = mergeSort(right);

            // System.out.println("After MS");

            BasicLinkedList<Integer> lst = merge(newLeft,newRight);
            //lst.print();
            return lst;
        }
    }

    public static ListNode<Integer> getMiddle(BasicLinkedList<Integer> original) {
        if (original.head == null) 
            return null;
        ListNode<Integer> slowPtr = original.head;
        ListNode<Integer> fastPtr = slowPtr.next;
        while (fastPtr != null) {
            fastPtr = fastPtr.next; 
            if(fastPtr!=null) {
                slowPtr = slowPtr.next; 
                fastPtr=fastPtr.next; 
            } 
        } 
        return slowPtr; 
    } 

    //Merges 2 non-empty lists together
    public static BasicLinkedList<Integer> merge(
        BasicLinkedList<Integer> firstList,
        BasicLinkedList<Integer> secondList) {
        ListNode<Integer> firstHead = firstList.head;
        ListNode<Integer> secondHead = secondList.head;

        BasicLinkedList<Integer> newList = new BasicLinkedList<Integer>();
        // move smaller node into newList, and maintain its tail

        //debugNode(firstHead,secondHead);
        if (firstHead.getElement() <= secondHead.getElement()) {
            newList.head = firstHead;
            firstHead = firstHead.getNext();
        } else {
            newList.head = secondHead;
            secondHead = secondHead.getNext();
        }
        ListNode<Integer> newTail = newList.head;


        while (firstHead != null && secondHead != null) {
            // System.out.println("Before loop ");
            // debugNode(firstHead,secondHead);
            if (firstHead.getElement() < secondHead.getElement()) {
                newTail.setNext(firstHead);
                firstHead = firstHead.getNext();
            } else {
                newTail.setNext(secondHead);
                secondHead = secondHead.getNext();
            }
            newTail = newTail.getNext();
            // System.out.println("After loop ");
            // debugNode(firstHead,secondHead);
        }

        if (firstHead != null)
            newTail.setNext(firstHead);
        if (secondHead != null)
            newTail.setNext(secondHead);
        // perform cleanup
        firstList.head = null;
        secondList.head = null;
        return newList;
    }

    public static void debug(BasicLinkedList<Integer> left, BasicLinkedList<Integer> right) {
        System.out.print("Left");
        left.print();
        System.out.print("Right");
        right.print();
    }

    public static void debugNode(ListNode<Integer> first, ListNode<Integer> second) {
        System.out.print("Left");
        System.out.println(first.getElement());
        System.out.print("Right");
        System.out.println(first.getElement());
    }



}

import java.util.*;

public interface LinkedListInterface <E> {

    public boolean  isEmpty( );
    public int      size ( );
    public E        getFirst  () throws NoSuchElementException; 
    public boolean  contains (E item);
    public void     addFirst (E item);
    public E        removeFirst ( ) throws NoSuchElementException;  

    public void     print ();

    // ....etc....
    // ....etc....
}

根据我的主驱动代码如图所示，具有正确的归并排序功能，List is: 1, 2 ,3, 4.应该在以[4,2,1,3]. 我当前的合并排序打印出 [1,3,2,4] 并且我的调试尝试显示在注释的代码行中。

标签： javasortinglinked-list

Answer 1

在 methodBasicLinkedList<Integer> mergeSort中，您没有设置链表的大小left，而是将链表的大小设置了right两次。

这是您的代码：

            right.head = nextOfMiddle;
            right.num_nodes = totalSize - newSize;
            //Create the left list, firstly by creating an empty shell and replace the head node
            BasicLinkedList<Integer> left = new BasicLinkedList();
            left.head = original.head;

            //here is the mistake
            //change it to  - left.num_nodes = newSize;
            right.num_nodes = newSize;

PS：我不知道你用的是哪个IDE，但我建议你下载IntelliJ Idea并使用它的调试功能。此外，您可能还有其他极端情况需要测试。