在java中合并排序链接列表的代码

Question

由于我使用的是Hackerrank代码，所以我不得不使用内部类。请检查代码，并让我知道这是否可以改进。

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class LinkedListMerge {

    private List<LinkedList<Integer>> listsToMerge;
    private LinkedList<Integer> mergedList;

    public LinkedListMerge() {
        listsToMerge = new ArrayList<LinkedList<Integer>>();
        listsToMerge.add(new LinkedList(new Integer[]{3, 5, 7, 10, 11}));
        listsToMerge.add(new LinkedList(new Integer[]{13, 25, 72, 101, 111}));
        listsToMerge.add(new LinkedList(new Integer[]{12, 15, 17, 110, 112}));

        mergedList = new LinkedList<Integer>();
    }

    public void mergeLists() {
        PriorityQueue<ValueIterator> priorityQueue = new PriorityQueue<ValueIterator>(listsToMerge.size());

        for(LinkedList<Integer> linkedList : listsToMerge) {
            Iterator<Node<Integer>> currentIterator = linkedList.iterator();
            priorityQueue.add(new ValueIterator(currentIterator.next().getValue(), currentIterator));
        }

        while(priorityQueue.peek() != null) {
            ValueIterator minElement = priorityQueue.poll();
            mergedList.add((Integer)minElement.getValue());
            if(minElement.getIterator().hasNext()) {
                Node<Integer> nextElement = ( Node<Integer>)minElement.getIterator().next();
                priorityQueue.add(new ValueIterator(nextElement.getValue(), minElement.getIterator()));
            }
        }

    }

    public LinkedList getMergedList() {
        return mergedList;
    }

    private class ValueIterator<K extends Comparable> implements Comparable {
        K value;
        Iterator<K> iterator;

        public ValueIterator(K value, Iterator<K> iterator) {
            this.value = value;
            this.iterator = iterator;
        }

        public K getValue() {
            return value;
        }

        public Iterator<K> getIterator() {
            return iterator;
        }

        @Override 
        public int compareTo(Object o) {
            return value.compareTo(((ValueIterator)o).getValue());
        }
    }

    public class LinkedList<K extends Comparable> {
        private Node<K> head = null;
        private Node<K> tail = null;

        public LinkedList() {

        }

        public LinkedList(K[] array) {
            head = new Node(array[0], null);

            Node<K> currentPointer = head;
            for(int i = 1; i < array.length; i++) {
                currentPointer.setNext(new Node(array[i], null));
                currentPointer = currentPointer.next();
            }
            tail = currentPointer;
        }

        public void add(K element) {
            if(head == null) {
                head = new Node(element, null);
                tail = head;
            } else {
                tail.setNext(new Node(element, null));
                tail = tail.next();
            }
        }

        public Iterator<Node<K>> iterator() {
            return new Itr(head);
        }

        @Override
        public String toString() {
            StringBuffer str = new StringBuffer();
            Iterator<Node<K>> itr = iterator();
            while(itr.hasNext()) {
                Node<K> current = itr.next();
                str.append(current.getValue().toString());
                str.append("->");
            }
            return str.toString();
        }

        private class Itr implements Iterator<Node<K>> {
            private Node<K> cursor;

            public Itr(Node<K> start) {
                cursor = start;
            }

            @Override
            public boolean hasNext() {
                return cursor !=null;
            }

            @Override
            public Node<K> next() {
                Node<K> currentElement = cursor;
                cursor = cursor.next();
                return currentElement;
            }

            @Override
            public void remove() {
                throw new RuntimeException("Unsupported Operation");
            }
        }

    }

    private class Node<K extends Comparable> {
        K data;
        Node next;

        public Node( K data, Node next) {
            this.data = data;
            this.next = next;
        }

        public void setNext(Node node) {
            next = node;
        }

        public Node<K> next() {
            return next;
        }

        public K getValue() {
            return data;
        }
    }

    public static void main(String args[]) {
        LinkedListMerge llm = new LinkedListMerge();
        llm.mergeLists();
        System.out.println(llm.getMergedList().toString());

    }
}

Answer 1

简化了

的实现

这是很多代码，可以做一些更简单的事情。

考虑这一备选实施：

• 给定两个列表的头节点
• 两个头都是非空的。
  • 比较头
  • 将值较小的节点追加到结果中。
  • 用较小的值推进头部

• 将非空的头追加到结果后面

如果有两个以上的列表要合并，应用该算法成对，重复，直到最后一个列表仍然包含所有合并的列表。

代码：

Node<K> MergeLists(Node<K> headA, Node<K> headB) {
    Node<K> dummy = new Node<>();
    Node<K> node = dummy;
    while (headA != null && headB != null) {
        if (headA.compareTo(headB) <= 0) {
            node.next = headA;
            headA = headA.next;
        } else {
            node.next = headB;
            headB = headB.next;
        }
        node = node.next;
    }
    if (headA != null) {
        node.next = headA;
    } else {
        node.next = headB;
    }
    return dummy.next;
}

注意，这个实现没有创建一个新的节点列表，但是它重写链接以形成一个新的链接列表。如果有必要，可以修改它以创建一个新列表。

组织可测试性

的代码

测试数据不属于LinkedListMerge的构造函数。这使得测试代码变得很困难。最好是为测试创建一个简单的入口点，例如，将2个(或更多)列表合并为参数的方法。