получение "sub-LinkedLlists" из Java-класса LinkedList (для целей MergeSort)

Question

Я пытаюсь применить алгоритм MergeSort на стандартном Java LinkedList . Я новичок в стандартных библиотеках.

Проблема, с которой я сталкиваюсь, - это создание 'sub-LinkedLists', чтобы получить максимальную производительность от MergeSort .

У меня есть рабочий код, но, к сожалению, он обрабатывает LinkedList , как если бы это был какой-то массив:

public void mergeSort(LinkedList<Integer> lisst) {
    if (lisst.size() < 2){
        return;
    }    
    int middleindex  = lisst.size()/2;    
    LinkedList<Integer> LeftList = new LinkedList<Integer>();


    for(int i = 0; i< middleindex; i++){    
        LeftList.addLast(lisst.get(i));
    }
    mergeSort(LeftList);

    LinkedList<Integer> RightList = new LinkedList<Integer>();

    for (int i = middleindex; i< lisst.size(); i++){    
        RightList.addLast(lisst.get(i));    
    }

    mergeSort(RightList);
    SortedMerge(RightList,LeftList,lisst);    
}

Из того, что я читал, выполнение подобных действий убивает цель сортировки слиянием в связанном списке. Но как я могу получить субсвязанные списки с объектом стандартного класса LinkedList? Я мог бы сделать это уверенно, если бы это было что-то, что я написал с классом узла как:

node leftHead = lisst.get(middleindex);
mergeSort(lefthead);// Assuming the method also takes a node instead of LL

но, читая библиотеку, я не могу понять, как указать на средний элемент и использовать остальное в качестве подсписка без зацикливания, чтобы добавить его в новый связанный список

Есть ли действительно простой способ сделать это? я не вижу ничего?

Спасибо вперед.

Answer 1

Если вам нужна только правая часть LinkedList, у вас должно быть следующее:

public static <T> LinkedList<T> removeUntil(LinkedList<T> list, int index) {
    for (int i = 0; i < index; i++) {
        list.removeFirst();
    }

    return list;
}

USECASE

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>(Arrays.asList(new Integer[] {1, 3, 5, 6, 9}));
    System.out.format("Input : %s%n", list);
    list = removeUntil(list, 3);
    System.out.format("Output: %s%n", list);
}

Использование прецедента

Input : [1, 3, 5, 6, 9]
Output: [6, 9]

---

Если вы хотите зарезервировать левую часть LinkedList, у вас должно быть следующее:

public static <T> LinkedList<T>[] split(LinkedList<T> list, int index) {
    LinkedList<T> left = new LinkedList<>();

    for (int i = 0; i < index; i++) {
        T t = list.removeFirst();
        left.addLast(t);
    }

    return new LinkedList[] {
        left, list
    };
}

USECASE

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>(Arrays.asList(new Integer[] {1, 3, 5, 6, 9}));
    System.out.format("Input : %s%n", list);
    LinkedList[] alist = split(list, 3);
    System.out.format("Output: %s, %s%n", alist[0], alist[1]);
}

Usecase output

Input : [1, 3, 5, 6, 9]
Output: [1, 3, 5], [6, 9]

Справка:

• LinkedList (Справочник по Java Platform SE 8 API)