java - Java中递归对LinkList进行合并排序

Question

所以任务是实现一个链表和对链表进行排序的合并排序。我完全意识到，在工业界我很可能不需要实现任何这些，但我觉得这是练习 Java 的好方法。这是我到目前为止所得到的:

节点类:

public class Node<E extends Comparable<E>>
    {

    public E data;
    public Node<E> next;

    public Node(E data)
    {
        this.data = data;
        next = null;
    }

    public void printData()
    {
        System.out.print(data + " ");
    }
}

LinkedList 类:

public class LinkedList<E extends Comparable<E>>
{

    protected Node<E> root;
    protected int size = 0;

    public LinkedList()
    {
        root = null;
    }


    public void addBeg(E e)
    {

        Node<E> newNode = new Node<E>(e);
        newNode.next = root;
        root = newNode;

        size++;
    }

    public Node deleteBeg()
    {
        Node<E> temp = root;
        if(!isEmpty())
        {
            root = root.next; 
            size--;
        }
        return temp;
    }

    public void setRoot(Node<E> newRoot)
    {
        root = newRoot;
    }

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

    public Node<E> getRoot()
    {
        return root;
    }

    public void printList()
    {
        Node<E> cur = root;   
        while(cur!=null)
            {
                cur.printData();
                cur=cur.next;
            }
        System.out.println();        
    }
}

合并排序器类:

public class MergeSorter<E extends Comparable<E>>
{

    public MergeSorter()
    {

    }

    private void split(LinkedList<E> list, LinkedList<E> firHalf, LinkedList<E> secHalf)
    {
        //if 0 or only 1 elements in the list - it doesn't seem to work, however
        if(list.getRoot() == null || list.getRoot().next == null)firHalf = list;
        else{
            Node<E> slow = list.getRoot(); 
            Node<E> fast = list.getRoot().next; 
            while(fast!=null)
            {
                fast = fast.next;
                if(fast!=null)
                {
                    fast = fast.next;
                    slow = slow.next;
                } 
            }
            //If I use the following line firHalf list is empty when in the caller of this method (it's not in this method, however). Don't understand why ):
            //firHalf = list; 
            firHalf.setRoot(list.getRoot());
            secHalf.setRoot(slow.next);
            slow.next = null;
        }

    }



    private LinkedList<E> merge(LinkedList<E> a, LinkedList<E> b)
     {
        LinkedList<E> mergedList = new LinkedList<E>();    
        Node<E> dummy = new Node<E>(null);
        Node<E> tail = dummy;

        while(true)
        {         
            if(a.getRoot() == null){
                tail.next = b.getRoot();
                break;
            }
            else if(b.getRoot() == null){
                tail.next = a.getRoot();
                break;
            }

            else 
            {
                if(a.getRoot().data.compareTo(b.getRoot().data) <= 0)
                {
                    tail.next = a.getRoot();
                    tail = tail.next;
                    a.setRoot(a.getRoot().next);
                }

                else
                {   
                    tail.next = b.getRoot();
                    tail = tail.next;
                    b.setRoot(b.getRoot().next);
                }
                tail.next = null;
            }

        }
        mergedList.setRoot(dummy.next);
        return mergedList;
    }

    public void mergeSort(LinkedList<E> list)
    {
        Node<E> root = list.getRoot();
        LinkedList<E> left  = new LinkedList<E>();
        LinkedList<E> right = new LinkedList<E>();

        if(root == null || root.next == null) return; //base case
        split(list, left, right); //split

        mergeSort(left);
        mergeSort(right);

        list = merge(left, right); // when this mergeSort returns this list should be  
                                   // referenced by the left or right variable of the 
                                   // current mergeSort call (but it isn't!)
    }
}

我对 Java 相当陌生(来自 C 背景)，所以如果我的代码完全错误，我提前表示诚挚的歉意。当我独立测试 MergeSorter 类中的拆分和合并方法时，一切似乎都有效(拆分由 0 或 1 个元素组成的列表不起作用，并且让我发疯，但这对于合并排序来说不是必需的)。然而， mergeSort 方法不起作用，我似乎无法找到方法。我尝试自己调试它，当两半合并到一个列表然后递归返回时似乎出现问题。新合并的列表应该由当前 mergeSort 调用的 left 或 right 变量引用，但我只得到最后一个元素而不是整个列表。

Answer 1

Java 中的方法参数始终按值传递。

这可能有点令人困惑，因为对象总是通过引用访问，因此您可能认为它们是通过引用传递的；但他们不是。相反，引用是按值传递的。

这意味着，像这样的方法:

public void methodThatDoesNothing(Object dst, Object src) {
    src = dst;
}

实际上什么也没做。它修改其局部变量 src 以引用与局部变量 dst 相同的对象，但这些只是局部变量，在函数返回时消失。它们与传递到方法中的任何变量或表达式完全分开。

所以，在你的代码中，这个:

firHalf = list;

实际上并没有做任何事情。我猜你想要的是:

while (! firHalf.isEmpty()) {
    firHalf.deleteBeg();
}
if (! list.isEmpty()) {
    firHalf.addBeg(list.root().data);
}

它修改由firHalf引用的对象，因此它具有与list相同的零或一个元素。