Недавно я изучил некоторые основы и нашел, что сортировка слияния связанного списка является довольно хорошей проблемой. Если у вас хорошая реализация, тогда покажите это здесь.
Слияние Сортировка связанного списка
Ответ 1
Интересно, почему это должно быть большой проблемой, как указано здесь, вот простая реализация на Java без каких-либо "хитрых уловок".
//The main function
public static Node merge_sort(Node head)
{
if(head == null || head.next == null)
return head;
Node middle = getMiddle(head); //get the middle of the list
Node left_head = head;
Node right_head = middle.next;
middle.next = null; //split the list into two halfs
return merge(merge_sort(left_head), merge_sort(right_head)); //recurse on that
}
//Merge subroutine to merge two sorted lists
public static Node merge(Node a, Node b)
{
Node dummyHead = new Node();
for(Node current = dummyHead; a != null && b != null; current = current.next;)
{
if(a.data <= b.data)
{
current.next = a;
a = a.next;
}
else
{
current.next = b;
b = b.next;
}
}
current.next = (a == null) ? b : a;
return dummyHead.next;
}
//Finding the middle element of the list for splitting
public static Node getMiddle(Node head)
{
if(head == null)
return head;
Node slow = head, fast = head;
while(fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
Ответ 2
Более простая/ясная реализация может быть рекурсивной реализацией, из которой время выполнения NLog (N) более понятно.
typedef struct _aList {
struct _aList* next;
struct _aList* prev; // Optional.
// some data
} aList;
aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
// Trivial case.
if (!list || !list->next)
return list;
aList *right = list,
*temp = list,
*last = list,
*result = 0,
*next = 0,
*tail = 0;
// Find halfway through the list (by running two pointers, one at twice the speed of the other).
while (temp && temp->next)
{
last = right;
right = right->next;
temp = temp->next->next;
}
// Break the list in two. (prev pointers are broken here, but we fix later)
last->next = 0;
// Recurse on the two smaller lists:
list = merge_sort_list_recursive(list, compare);
right = merge_sort_list_recursive(right, compare);
// Merge:
while (list || right)
{
// Take from empty lists, or compare:
if (!right) {
next = list;
list = list->next;
} else if (!list) {
next = right;
right = right->next;
} else if (compare(list, right) < 0) {
next = list;
list = list->next;
} else {
next = right;
right = right->next;
}
if (!result) {
result=next;
} else {
tail->next=next;
}
next->prev = tail; // Optional.
tail = next;
}
return result;
}
Примечание. Для рекурсии это требование хранения журнала (N). Производительность должна быть примерно сопоставима с другой стратегией, которую я опубликовал. Здесь существует потенциальная оптимизация, запуская цикл слияния while (list && right) и просто добавляя оставшийся список (поскольку мы не очень заботимся о конце списков, зная, что они объединены достаточно).
Ответ 3
Тяжело основано на коде EXCELLENT: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
Немного обработано и прибрано:
typedef struct _aList {
struct _aList* next;
struct _aList* prev; // Optional.
// some data
} aList;
aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
int listSize=1,numMerges,leftSize,rightSize;
aList *tail,*left,*right,*next;
if (!list || !list->next) return list; // Trivial case
do { // For each power of two<=list length
numMerges=0,left=list;tail=list=0; // Start at the start
while (left) { // Do this list_len/listSize times:
numMerges++,right=left,leftSize=0,rightSize=listSize;
// Cut list into two halves (but don't overrun)
while (right && leftSize<listSize) leftSize++,right=right->next;
// Run through the lists appending onto what we have so far.
while (leftSize>0 || (rightSize>0 && right)) {
// Left empty, take right OR Right empty, take left, OR compare.
if (!leftSize) {next=right;right=right->next;rightSize--;}
else if (!rightSize || !right) {next=left;left=left->next;leftSize--;}
else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
else {next=right;right=right->next;rightSize--;}
// Update pointers to keep track of where we are:
if (tail) tail->next=next; else list=next;
// Sort prev pointer
next->prev=tail; // Optional.
tail=next;
}
// Right is now AFTER the list we just sorted, so start the next sort there.
left=right;
}
// Terminate the list, double the list-sort size.
tail->next=0,listSize<<=1;
} while (numMerges>1); // If we only did one merge, then we just sorted the whole list.
return list;
}
NB: это O (NLog (N)) гарантировано и использует O (1) ресурсы (без рекурсии, без стека, ничего).
Ответ 4
Один интересный способ состоит в том, чтобы поддерживать стек и сливаться только в том случае, если в списке в стеке одинаковое количество элементов, и в противном случае нажмите список, пока не закончите элементы во входящем списке, а затем слейте стек.
Ответ 5
Самый простой из Справочник по алгоритмам Gonnet + Baeza Yates. Вы вызываете его с количеством отсортированных элементов, которые вы хотите, которые рекурсивно делятся пополам до тех пор, пока не достигнет запроса для списка размера один, который вы затем просто очистите перед первоначальным списком. Все они объединяются в полноразмерный отсортированный список.
[Обратите внимание, что класс, основанный на стеке в первом столбце, называется онлайн-сетью и он получает самое маленькое упоминание в упражнении в Knuth Vol 3]
Ответ 6
Здесь альтернативная рекурсивная версия. Это не нужно делать по списку, чтобы разделить его: мы снабжаем указатель на элемент head (который не является частью сортировки) и длину, а рекурсивная функция возвращает указатель на конец отсортированного списка.
element* mergesort(element *head,long lengtho)
{
long count1=(lengtho/2), count2=(lengtho-count1);
element *next1,*next2,*tail1,*tail2,*tail;
if (lengtho<=1) return head->next; /* Trivial case. */
tail1 = mergesort(head,count1);
tail2 = mergesort(tail1,count2);
tail=head;
next1 = head->next;
next2 = tail1->next;
tail1->next = tail2->next; /* in case this ends up as the tail */
while (1) {
if(cmp(next1,next2)<=0) {
tail->next=next1; tail=next1;
if(--count1==0) { tail->next=next2; return tail2; }
next1=next1->next;
} else {
tail->next=next2; tail=next2;
if(--count2==0) { tail->next=next1; return tail1; }
next2=next2->next;
}
}
}
Ответ 7
Я был одержим оптимизацией беспорядка для этого алгоритма, и ниже - это то, к чему я наконец пришел. Много другого кода в Интернете и StackOverflow ужасно плохо. Есть люди, пытающиеся получить среднюю точку списка, делая рекурсию, имея несколько циклов для оставшихся узлов, поддерживая подсчеты тонны вещей - ВСЕ это не нужно. MergeSort естественно подходит для связанного списка, и алгоритм может быть красивым и компактным, но это не так просто, чтобы добраться до этого состояния.
Ниже код поддерживает минимальное количество переменных и имеет минимальное количество логических шагов, необходимых для алгоритма (т.е. не делая код недостижимым/нечитаемым), насколько я знаю. Однако я не пытался минимизировать LOC и сохранял столько свободного места, сколько необходимо, чтобы сохранить читаемость. Я тестировал этот код через довольно строгие модульные тесты.
Обратите внимание, что этот ответ объединяет несколько методов из другого ответа fooobar.com/questions/108990/.... Хотя код находится в С#, он должен быть тривиальным для преобразования в С++, Java и т.д.
SingleListNode<T> SortLinkedList<T>(SingleListNode<T> head) where T : IComparable<T>
{
int blockSize = 1, blockCount;
do
{
//Maintain two lists pointing to two blocks, left and right
SingleListNode<T> left = head, right = head, tail = null;
head = null; //Start a new list
blockCount = 0;
//Walk through entire list in blocks of size blockCount
while (left != null)
{
blockCount++;
//Advance right to start of next block, measure size of left list while doing so
int leftSize = 0, rightSize = blockSize;
for (;leftSize < blockSize && right != null; ++leftSize)
right = right.Next;
//Merge two list until their individual ends
bool leftEmpty = leftSize == 0, rightEmpty = rightSize == 0 || right == null;
while (!leftEmpty || !rightEmpty)
{
SingleListNode<T> smaller;
//Using <= instead of < gives us sort stability
if (rightEmpty || (!leftEmpty && left.Value.CompareTo(right.Value) <= 0))
{
smaller = left; left = left.Next; --leftSize;
leftEmpty = leftSize == 0;
}
else
{
smaller = right; right = right.Next; --rightSize;
rightEmpty = rightSize == 0 || right == null;
}
//Update new list
if (tail != null)
tail.Next = smaller;
else
head = smaller;
tail = smaller;
}
//right now points to next block for left
left = right;
}
//terminate new list, take care of case when input list is null
if (tail != null)
tail.Next = null;
//Lg n iterations
blockSize <<= 1;
} while (blockCount > 1);
return head;
}
Достопримечательности
- Не существует специальной обработки для таких случаев, как нулевой список из списка 1 и т.д. Эти случаи "просто работают".
- У многих "стандартных" алгоритмов тексты имеют две петли, чтобы пройти оставшиеся элементы, чтобы обрабатывать случай, когда один список короче другого. Выше код устраняет необходимость в нем.
- Мы уверены, что сортировка стабильная
- Внутренний цикл while, который является горячей точкой, оценивает в среднем три выражения на итерацию, которые, как мне кажется, минимальны.
Обновление: @ideasman42 имеет переведенный выше код на C/С++, а также предложения по исправлению комментариев и еще большему улучшению. Выше код теперь обновляется с этими данными.
Ответ 8
Я решил проверить примеры здесь, а также еще один подход, первоначально написанный Джонатаном Каннингемом в Pop-11. Я закодировал все подходы в С# и сделал сравнение с различными размерами списков. Я сравнил подход Mono eglib от Raja R Harinath, код С# от Shital Shah, подход Java Jayadev, рекурсивные и нерекурсивные версии Дэвида Гэмбла, первого кода C от Ed Wynn (это разбилось с моим образцом набора данных, Я не отлаживал), и версию Каннингема. Полный код здесь: https://gist.github.com/314e572808f29adb0e41.git.
Mono eglib основан на аналогичной идее для Каннингема и имеет сопоставимую скорость, если только список не сортируется уже, и в этом случае подход Каннингема намного быстрее (если его частично отсортировать, eglib немного быстрее). Код eglib использует фиксированную таблицу для хранения рекурсии сортировки слияния, тогда как подход Каннингема работает с использованием возрастающих уровней рекурсии - поэтому он начинается без рекурсии, затем с 1-ой рекурсией, затем с 2-глубоной рекурсией и т.д. Согласно сколько шагов требуется для сортировки. Я нахожу код Каннингема немного легче следовать, и нет никаких догадок, связанных с тем, насколько велика таблица рекурсии, поэтому она получает мой голос. Другие подходы, которые я пробовал на этой странице, были в два или более раза медленнее.
Вот порт С# для сортировки Pop-11:
/// <summary>
/// Sort a linked list in place. Returns the sorted list.
/// Originally by Jonathan Cunningham in Pop-11, May 1981.
/// Ported to C# by Jon Meyer.
/// </summary>
public class ListSorter<T> where T : IComparable<T> {
SingleListNode<T> workNode = new SingleListNode<T>(default(T));
SingleListNode<T> list;
/// <summary>
/// Sorts a linked list. Returns the sorted list.
/// </summary>
public SingleListNode<T> Sort(SingleListNode<T> head) {
if (head == null) throw new NullReferenceException("head");
list = head;
var run = GetRun(); // get first run
// As we progress, we increase the recursion depth.
var n = 1;
while (list != null) {
var run2 = GetSequence(n);
run = Merge(run, run2);
n++;
}
return run;
}
// Get the longest run of ordered elements from list.
// The run is returned, and list is updated to point to the
// first out-of-order element.
SingleListNode<T> GetRun() {
var run = list; // the return result is the original list
var prevNode = list;
var prevItem = list.Value;
list = list.Next; // advance to the next item
while (list != null) {
var comp = prevItem.CompareTo(list.Value);
if (comp > 0) {
// reached end of sequence
prevNode.Next = null;
break;
}
prevItem = list.Value;
prevNode = list;
list = list.Next;
}
return run;
}
// Generates a sequence of Merge and GetRun() operations.
// If n is 1, returns GetRun()
// If n is 2, returns Merge(GetRun(), GetRun())
// If n is 3, returns Merge(Merge(GetRun(), GetRun()),
// Merge(GetRun(), GetRun()))
// and so on.
SingleListNode<T> GetSequence(int n) {
if (n < 2) {
return GetRun();
} else {
n--;
var run1 = GetSequence(n);
if (list == null) return run1;
var run2 = GetSequence(n);
return Merge(run1, run2);
}
}
// Given two ordered lists this returns a list that is the
// result of merging the two lists in-place (modifying the pairs
// in list1 and list2).
SingleListNode<T> Merge(SingleListNode<T> list1, SingleListNode<T> list2) {
// we reuse a single work node to hold the result.
// Simplifies the number of test cases in the code below.
var prevNode = workNode;
while (true) {
if (list1.Value.CompareTo(list2.Value) <= 0) {
// list1 goes first
prevNode.Next = list1;
prevNode = list1;
if ((list1 = list1.Next) == null) {
// reached end of list1 - join list2 to prevNode
prevNode.Next = list2;
break;
}
} else { // same but for list2
prevNode.Next = list2;
prevNode = list2;
if ((list2 = list2.Next) == null) {
prevNode.Next = list1;
break;
}
}
}
// the result is in the back of the workNode
return workNode.Next;
}
}
Ответ 9
Вот моя реализация Knuth "Сортировка слияния списков" (Алгоритм 5.2.4L из Vol.3 TAOCP, 2-е изд.). Я добавлю несколько комментариев в конце, но здесь резюме:
На случайном входе он работает немного быстрее, чем код Саймона Татхама (см. нерекурсивный ответ Dave Gamble со ссылкой), но немного медленнее, чем рекурсивный код Dave Gamble. Это труднее понять, чем любой другой. По крайней мере, в моей реализации каждый элемент должен иметь два указателя на элементы. (Альтернативой может быть один указатель и логический флаг.) Таким образом, это, вероятно, не очень полезный подход. Однако одна отличительная точка заключается в том, что он работает очень быстро, если вход имеет длинные отрезки, которые уже отсортированы.
element *knuthsort(element *list)
{ /* This is my attempt at implementing Knuth Algorithm 5.2.4L "List merge sort"
from Vol.3 of TAOCP, 2nd ed. */
element *p, *pnext, *q, *qnext, head1, head2, *s, *t;
if(!list) return NULL;
L1: /* This is the clever L1 from exercise 12, p.167, solution p.647. */
head1.next=list;
t=&head2;
for(p=list, pnext=p->next; pnext; p=pnext, pnext=p->next) {
if( cmp(p,pnext) > 0 ) { t->next=NULL; t->spare=pnext; t=p; }
}
t->next=NULL; t->spare=NULL; p->spare=NULL;
head2.next=head2.spare;
L2: /* begin a new pass: */
t=&head2;
q=t->next;
if(!q) return head1.next;
s=&head1;
p=s->next;
L3: /* compare: */
if( cmp(p,q) > 0 ) goto L6;
L4: /* add p onto the current end, s: */
if(s->next) s->next=p; else s->spare=p;
s=p;
if(p->next) { p=p->next; goto L3; }
else p=p->spare;
L5: /* complete the sublist by adding q and all its successors: */
s->next=q; s=t;
for(qnext=q->next; qnext; q=qnext, qnext=q->next);
t=q; q=q->spare;
goto L8;
L6: /* add q onto the current end, s: */
if(s->next) s->next=q; else s->spare=q;
s=q;
if(q->next) { q=q->next; goto L3; }
else q=q->spare;
L7: /* complete the sublist by adding p and all its successors: */
s->next=p;
s=t;
for(pnext=p->next; pnext; p=pnext, pnext=p->next);
t=p; p=p->spare;
L8: /* is this end of the pass? */
if(q) goto L3;
if(s->next) s->next=p; else s->spare=p;
t->next=NULL; t->spare=NULL;
goto L2;
}
Ответ 10
Там есть нерекурсивный объединенный список слияния в mono eglib.
Основная идея состоит в том, что цикл управления для различных объединений параллелен побитовому приращению двоичного целого. O (n) сливается с "вставкой" n узлов в дерево слияния, а ранг этих слияний соответствует двоичной цифре, которая увеличивается. Используя эту аналогию, нужно только материализовать только O (log n) узлы дерева слияния во временный массив хранения.
Ответ 11
Другой пример нерекурсивной сортировки слияния для связанных списков, где функции не являются частью класса. Этот пример кода и HP/Microsoft std:: list:: sort используют один и тот же базовый алгоритм. Невысокая, не рекурсивная сортировка слияния, которая использует малый (от 26 до 32) массив указателей к первым узлам списка, где array [i] либо равен 0, либо указывает на список размера 2 на мощность i, В моей системе Intel 2600K 3.4ghz он может сортировать 4 миллиона узлов с 32-разрядными целыми без знака в качестве данных примерно за 1 секунду.
NODE * MergeLists(NODE *, NODE *); /* prototype */
/* sort a list using array of pointers to list */
/* aList[i] == NULL or ptr to list with 2^i nodes */
#define NUMLISTS 32 /* number of lists */
NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS]; /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
if(pList == NULL) /* check for empty list */
return NULL;
for(i = 0; i < NUMLISTS; i++) /* init array */
aList[i] = NULL;
pNode = pList; /* merge nodes into array */
while(pNode != NULL){
pNext = pNode->next;
pNode->next = NULL;
for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
pNode = MergeLists(aList[i], pNode);
aList[i] = NULL;
}
if(i == NUMLISTS) /* don't go beyond end of array */
i--;
aList[i] = pNode;
pNode = pNext;
}
pNode = NULL; /* merge array into one list */
for(i = 0; i < NUMLISTS; i++)
pNode = MergeLists(aList[i], pNode);
return pNode;
}
/* merge two already sorted lists */
/* compare uses pSrc2 < pSrc1 to follow the STL rule */
/* of only using < and not <= */
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL; /* destination head ptr */
NODE **ppDst = &pDst; /* ptr to head or prev->next */
if(pSrc1 == NULL)
return pSrc2;
if(pSrc2 == NULL)
return pSrc1;
while(1){
if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */
*ppDst = pSrc2;
pSrc2 = *(ppDst = &(pSrc2->next));
if(pSrc2 == NULL){
*ppDst = pSrc1;
break;
}
} else { /* src1 <= src2 */
*ppDst = pSrc1;
pSrc1 = *(ppDst = &(pSrc1->next));
if(pSrc1 == NULL){
*ppDst = pSrc2;
break;
}
}
}
return pDst;
}
Ответ 12
Это целая часть кода, которая показывает, как мы можем создать список ссылок в java и отсортировать его с помощью сортировки Merge. Я создаю node в классе MergeNode, и есть еще один класс MergesortLinklist, где есть логика разделения и объединения.
class MergeNode {
Object value;
MergeNode next;
MergeNode(Object val) {
value = val;
next = null;
}
MergeNode() {
value = null;
next = null;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public MergeNode getNext() {
return next;
}
public void setNext(MergeNode next) {
this.next = next;
}
@Override
public String toString() {
return "MergeNode [value=" + value + ", next=" + next + "]";
}
}
public class MergesortLinkList {
MergeNode head;
static int totalnode;
public MergeNode getHead() {
return head;
}
public void setHead(MergeNode head) {
this.head = head;
}
MergeNode add(int i) {
// TODO Auto-generated method stub
if (head == null) {
head = new MergeNode(i);
// System.out.println("head value is "+head);
return head;
}
MergeNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new MergeNode(i);
return head;
}
MergeNode mergesort(MergeNode nl1) {
// TODO Auto-generated method stub
if (nl1.next == null) {
return nl1;
}
int counter = 0;
MergeNode temp = nl1;
while (temp != null) {
counter++;
temp = temp.next;
}
System.out.println("total nodes " + counter);
int middle = (counter - 1) / 2;
temp = nl1;
MergeNode left = nl1, right = nl1;
int leftindex = 0, rightindex = 0;
if (middle == leftindex) {
right = left.next;
}
while (leftindex < middle) {
leftindex++;
left = left.next;
right = left.next;
}
left.next = null;
left = nl1;
System.out.println(left.toString());
System.out.println(right.toString());
MergeNode p1 = mergesort(left);
MergeNode p2 = mergesort(right);
MergeNode node = merge(p1, p2);
return node;
}
MergeNode merge(MergeNode p1, MergeNode p2) {
// TODO Auto-generated method stub
MergeNode L = p1;
MergeNode R = p2;
int Lcount = 0, Rcount = 0;
MergeNode tempnode = null;
while (L != null && R != null) {
int val1 = (int) L.value;
int val2 = (int) R.value;
if (val1 > val2) {
if (tempnode == null) {
tempnode = new MergeNode(val2);
R = R.next;
} else {
MergeNode store = tempnode;
while (store.next != null) {
store = store.next;
}
store.next = new MergeNode(val2);
R = R.next;
}
} else {
if (tempnode == null) {
tempnode = new MergeNode(val1);
L = L.next;
} else {
MergeNode store = tempnode;
while (store.next != null) {
store = store.next;
}
store.next = new MergeNode(val1);
L = L.next;
}
}
}
MergeNode handle = tempnode;
while (L != null) {
while (handle.next != null) {
handle = handle.next;
}
handle.next = L;
L = null;
}
// Copy remaining elements of L[] if any
while (R != null) {
while (handle.next != null) {
handle = handle.next;
}
handle.next = R;
R = null;
}
System.out.println("----------------sorted value-----------");
System.out.println(tempnode.toString());
return tempnode;
}
public static void main(String[] args) {
MergesortLinkList objsort = new MergesortLinkList();
MergeNode n1 = objsort.add(9);
MergeNode n2 = objsort.add(7);
MergeNode n3 = objsort.add(6);
MergeNode n4 = objsort.add(87);
MergeNode n5 = objsort.add(16);
MergeNode n6 = objsort.add(81);
MergeNode n7 = objsort.add(21);
MergeNode n8 = objsort.add(16);
MergeNode n9 = objsort.add(99);
MergeNode n10 = objsort.add(31);
MergeNode val = objsort.mergesort(n1);
System.out.println("===============sorted values=====================");
while (val != null) {
System.out.println(" value is " + val.value);
val = val.next;
}
}
}
Ответ 13
Я не вижу никаких решений C++, размещенных здесь. Итак, вот и все. Надеюсь, это кому-нибудь поможет.
class Solution {
public:
ListNode *merge(ListNode *left, ListNode *right){
ListNode *head = NULL, *temp = NULL;
// Find which one is the head node for the merged list
if(left->val <= right->val){
head = left, temp = left;
left = left->next;
}
else{
head = right, temp = right;
right = right->next;
}
while(left && right){
if(left->val <= right->val){
temp->next = left;
temp = left;
left = left->next;
}
else{
temp->next = right;
temp = right;
right = right->next;
}
}
// If some elements still left in the left or the right list
if(left)
temp->next = left;
if(right)
temp->next = right;
return head;
}
ListNode* sortList(ListNode* head){
if(!head || !head->next)
return head;
// Find the length of the list
int length = 0;
ListNode *temp = head;
while(temp){
length++;
temp = temp->next;
}
// Reset temp
temp = head;
// Store half of it in left and the other half in right
// Create two lists and sort them
ListNode *left = temp, *prev = NULL;
int i = 0, mid = length / 2;
// Left list
while(i < mid){
prev = temp;
temp = temp->next;
i++;
}
// The end of the left list should point to NULL
if(prev)
prev->next = NULL;
// Right list
ListNode *right = temp;
// Sort left list
ListNode *sortedLeft = sortList(left);
// Sort right list
ListNode *sortedRight = sortList(right);
// Merge them
ListNode *sortedList = merge(sortedLeft, sortedRight);
return sortedList;
}
};
Ответ 14
Вот Java-реализация сортировки слиянием в связанном списке:
- Сложность времени: O (n.logn)
- Сложность пространства: O (1) - реализация сортировки слиянием в связанном списке позволяет избежать затрат на вспомогательное хранение O (n), обычно связанных с алгоритмом
class Solution
{
public ListNode mergeSortList(ListNode head)
{
if(head == null || head.next == null)
return head;
ListNode mid = getMid(head), second_head = mid.next; mid.next = null;
return merge(mergeSortList(head), mergeSortList(second_head));
}
private ListNode merge(ListNode head1, ListNode head2)
{
ListNode result = new ListNode(0), current = result;
while(head1 != null && head2 != null)
{
if(head1.val < head2.val)
{
current.next = head1;
head1 = head1.next;
}
else
{
current.next = head2;
head2 = head2.next;
}
current = current.next;
}
if(head1 != null) current.next = head1;
if(head2 != null) current.next = head2;
return result.next;
}
private ListNode getMid(ListNode head)
{
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Ответ 15
Проверенная рабочая версия C++ единого связанного списка, основанная на ответе с наибольшим количеством голосов.
singlelinkedlist.h:
#pragma once
#include <stdexcept>
#include <iostream>
#include <initializer_list>
namespace ythlearn{
template<typename T>
class Linkedlist{
public:
class Node{
public:
Node* next;
T elem;
};
Node head;
int _size;
public:
Linkedlist(){
head.next = nullptr;
_size = 0;
}
Linkedlist(std::initializer_list<T> init_list){
head.next = nullptr;
_size = 0;
for(auto s = init_list.begin(); s!=init_list.end(); s++){
push_left(*s);
}
}
int size(){
return _size;
}
bool isEmpty(){
return size() == 0;
}
bool isSorted(){
Node* n_ptr = head.next;
while(n_ptr->next != nullptr){
if(n_ptr->elem > n_ptr->next->elem)
return false;
n_ptr = n_ptr->next;
}
return true;
}
Linkedlist& push_left(T elem){
Node* n = new Node;
n->elem = elem;
n->next = head.next;
head.next = n;
++_size;
return *this;
}
void print(){
Node* loopPtr = head.next;
while(loopPtr != nullptr){
std::cout << loopPtr->elem << " ";
loopPtr = loopPtr->next;
}
std::cout << std::endl;
}
void call_merge(){
head.next = merge_sort(head.next);
}
Node* merge_sort(Node* n){
if(n == nullptr || n->next == nullptr)
return n;
Node* middle = getMiddle(n);
Node* left_head = n;
Node* right_head = middle->next;
middle->next = nullptr;
return merge(merge_sort(left_head), merge_sort(right_head));
}
Node* getMiddle(Node* n){
if(n == nullptr)
return n;
Node* slow, *fast;
slow = fast = n;
while(fast->next != nullptr && fast->next->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
Node* merge(Node* a, Node* b){
Node dummyHead;
Node* current = &dummyHead;
while(a != nullptr && b != nullptr){
if(a->elem < b->elem){
current->next = a;
a = a->next;
}else{
current->next = b;
b = b->next;
}
current = current->next;
}
current->next = (a == nullptr) ? b : a;
return dummyHead.next;
}
Linkedlist(const Linkedlist&) = delete;
Linkedlist& operator=(const Linkedlist&) const = delete;
~Linkedlist(){
Node* node_to_delete;
Node* ptr = head.next;
while(ptr != nullptr){
node_to_delete = ptr;
ptr = ptr->next;
delete node_to_delete;
}
}
};
}
main.cpp:
#include <iostream>
#include <cassert>
#include "singlelinkedlist.h"
using namespace std;
using namespace ythlearn;
int main(){
Linkedlist<int> l = {3,6,-5,222,495,-129,0};
l.print();
l.call_merge();
l.print();
assert(l.isSorted());
return 0;
}
Ответ 16
Простейшая реализация Java:
Сложность времени: O (nLogn) n = количество узлов. Каждая итерация по связанному списку удваивает размер отсортированных меньших связанных списков. Например, после первой итерации связанный список будет отсортирован на две половины. После второй итерации связанный список будет отсортирован на четыре половины. Он будет продолжать сортировку по размеру связанного списка. Для достижения первоначального размера связанного списка потребуется O (logn) удвоений размеров небольших связанных списков. N в nlogn есть, потому что каждая итерация связанного списка займет время, пропорциональное количеству узлов в исходном связанном списке.
class Node {
int data;
Node next;
Node(int d) {
data = d;
}
}
class LinkedList {
Node head;
public Node mergesort(Node head) {
if(head == null || head.next == null) return head;
Node middle = middle(head), middle_next = middle.next;
middle.next = null;
Node left = mergesort(head), right = mergesort(middle_next), node = merge(left, right);
return node;
}
public Node merge(Node first, Node second) {
Node node = null;
if (first == null) return second;
else if (second == null) return first;
else if (first.data <= second.data) {
node = first;
node.next = merge(first.next, second);
} else {
node = second;
node.next = merge(first, second.next);
}
return node;
}
public Node middle(Node head) {
if (head == null) return head;
Node second = head, first = head.next;
while(first != null) {
first = first.next;
if (first != null) {
second = second.next;
first = first.next;
}
}
return second;
}
}
Ответ 17
Вы можете использовать эту реализацию сортировки слияния и написать свои собственные функции для взаимодействия со связанным списком, как если бы это был массив.
Ответ 18
Одним из недостатков сортировки слияния является то, что он использует пространство O (n) для хранения данных. т.е. при объединении двух подписок для связанного списка, этого можно избежать, продолжая изменять следующий указатель в списке node. Последняя реализация кажется опрятной, но не учитывает ее.
Ответ 19
public int[] msort(int[] a) {
if (a.Length > 1) {
int min = a.Length / 2;
int max = min;
int[] b = new int[min];
int[] c = new int[max]; // dividing main array into two half arrays
for (int i = 0; i < min; i++) {
b[i] = a[i];
}
for (int i = min; i < min + max; i++) {
c[i - min] = a[i];
}
b = msort(b);
c = msort(c);
int x = 0;
int y = 0;
int z = 0;
while (b.Length != y && c.Length != z) {
if (b[y] < c[z]) {
a[x] = b[y];
//r--
x++;
y++;
} else {
a[x] = c[z];
x++;
z++;
}
}
while (b.Length != y) {
a[x] = b[y];
x++;
y++;
}
while (c.Length != z) {
a[x] = c[z];
x++;
z++;
}
}
return a;
}