java - 链表合并排序的实现

java - 链表合并排序的实现,第1张

我正在尝试一个在线发现的问题,该问题是使用链接列表实现合并排序,但是使用了我学校教授的奇怪列表接口实现,而不是仅使用节点,因此从其他解决方案进行的普通复制在这里不起作用。我通常只是在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],并且我的调试尝试显示在代码的注释行中。

最佳答案:

1 个答案:

答案 0 :(得分:0)

在方法BasicLinkedList<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并使用其调试功能。另外,您可能还需要测试其他极端情况。

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复