blocks|key|1223015|text|不是你问题的直接答案，但如果你使用Skip+List，它已经被排序，搜索时间为O(log+)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1223016|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Skip_list^0|H|9|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Not a direct answer to your question, but if you use a <a href="http://en.wikipedia.org/wiki/Skip_list" rel="nofollow noreferrer">Skip List</a>, it is already sorted and has O(log N) search time.

blocks|key|1437937|text|Mergesort是你在这里能做的最好的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1437938|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Mergesort is the best you can do here.

blocks|key|1223140|text|据我所知，最好的排序算法是O(n*log+n)，无论容器是什么-已经证明，在广义的单词(合并排序/快速排序等样式)中的排序不能更低。使用链表不会给你带来更好的运行时间。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1223141|运行在O(n)中的唯一算法是"hack“算法，它依赖于计数值，而不是实际排序。|1223142|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

As I know, the best sorting algorithm is O(n*log n), whatever the container - it's been proved that sorting in the broad sense of the word (mergesort/quicksort etc style) can't go lower. Using a linked list will not give you a better run time. 

The only one algorithm which runs in O(n) is a "hack" algorithm which relies on counting values rather than actually sorting.

blocks|key|1223266|text|合并排序不需要O(1)访问，并且是O(N+ln+N+)。对于一般数据，没有比O(N+ln+N+)更好的排序算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1223267|特殊的数据算法，如基数排序(限制数据大小)或直方图排序(计算离散数据)，可以用较低的增长函数对链表进行排序，只要使用具有O(1)访问权限的不同结构作为临时存储即可。|1223268|另一类特殊数据是具有k个无序元素的几乎排序列表的比较排序。这可以在O(+kn+)操作中排序。|1223269|将列表复制到数组并返回将是O(N)，因此，如果空间不是问题，则可以使用任何排序算法。|1223270|例如，给定一个包含uint_8的链表，此代码将使用直方图排序在O(N)时间内对其进行排序：|offset|length|style|CODE|1223271|#include+<stdio.h>
#include+<stdint.h>
#include+<malloc.h>

typedef+struct+_list+list_t;
struct+_list+{
++++uint8_t+value;
++++list_t++*next;
};


list_t*+sort_list+(+list_t*+list+)
{
++++list_t*+heads[257]+=+{0};
++++list_t*+tails[257]+=+{0};

++++//+O(N)+loop
++++for+(+list_t*+it+=+list;+it+!=+0;+it+=+it+->+next+)+{
++++++++list_t*+next+=+it+->+next;

++++++++if+(+heads[+it+->+value+]+==+0+)+{
++++++++++++heads[+it+->+value+]+=+it;
++++++++}+else+{
++++++++++++tails[+it+->+value+]+->+next+=+it;
++++++++}

++++++++tails[+it+->+value+]+=+it;
++++}

++++list_t*+result+=+0;

++++//+constant+time+loop
++++for+(+size_t+i+=+255;+i--+>+0;+)+{
++++++++if+(+tails[i]+)+{
++++++++++++tails[i]+->+next+=+result;
++++++++++++result+=+heads[i];
++++++++}
++++}

++++return+result;
}

list_t*+make_list+(+char*+string+)
{
++++list_t+head;

++++for+(+list_t*+it+=+&head;+*string;+it+=+it+->+next,+%2B%2Bstring+)+{
++++++++it+->+next+=+malloc+(+sizeof+(+list_t+)+);
++++++++it+->+next+->+value+=+(+uint8_t+)+*+string;
++++++++it+->+next+->+next+=+0;
++++}

++++return+head.next;
}

void+free_list+(+list_t*+list+)
{
++++for+(+list_t*+it+=+list;+it+!=+0;+)+{
++++++++list_t*+next+=+it+->+next;
++++++++free+(+it+);
++++++++it+=+next;
++++}
}

void+print_list+(+list_t*+list+)
{
++++printf+(+"[+"+);

++++if+(+list+)+{
++++++++printf+(+"%25c",+list+->+value+);

++++++++for+(+list_t*+it+=+list+->+next;+it+!=+0;+it+=+it+->+next+)
++++++++++++printf+(+",+%25c",+it+->+value+);
++++}

++++printf+(+"+]\n"+);
}


int+main+(+int+nargs,+char**+args+)
{
++++list_t*+list+=+make_list+(+nargs+>+1+?+args[1]+:+"wibble"+);


++++print_list+(+list+);

++++list_t*+sorted+=+sort_list+(+list+);


++++print_list+(+sorted+);

++++free_list+(+list+);
}|code-block|syntax|javascript|1223272|entityMap^0|0|0|0|0|9|6|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|X|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|Y|8|@$J|Z|K|10|L|M]]|9|@]|A|$]]|$1|N|3|O|5|P|7|11|8|@]|9|@]|A|$Q|R]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

Merge sort doesn't require O(1) access and is O ( n ln n ). No known algorithms for sorting general data are better than O ( n ln n ).

The special data algorithms such as radix sort ( limits size of data ) or histogram sort ( counts discrete data ) could sort a linked list with a lower growth function, as long as you use a different structure with O(1) access as temporary storage. 

Another class of special data is a comparison sort of an almost sorted list with k elements out of order. This can be sorted in O ( kn ) operations.

Copying the list to an array and back would be O(N), so any sorting algorithm can be used if space is not an issue.

For example, given a linked list containing <code>uint_8</code>, this code will sort it in O(N) time using a histogram sort:

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdint.h&gt;
#include &lt;malloc.h&gt;

typedef struct _list list_t;
struct _list {
 uint8_t value;
 list_t *next;
};


list_t* sort_list ( list_t* list )
{
 list_t* heads[257] = {0};
 list_t* tails[257] = {0};

 // O(N) loop
 for ( list_t* it = list; it != 0; it = it -&gt; next ) {
 list_t* next = it -&gt; next;

 if ( heads[ it -&gt; value ] == 0 ) {
 heads[ it -&gt; value ] = it;
 } else {
 tails[ it -&gt; value ] -&gt; next = it;
 }

 tails[ it -&gt; value ] = it;
 }

 list_t* result = 0;

 // constant time loop
 for ( size_t i = 255; i-- &gt; 0; ) {
 if ( tails[i] ) {
 tails[i] -&gt; next = result;
 result = heads[i];
 }
 }

 return result;
}

list_t* make_list ( char* string )
{
 list_t head;

 for ( list_t* it = &amp;head; *string; it = it -&gt; next, ++string ) {
 it -&gt; next = malloc ( sizeof ( list_t ) );
 it -&gt; next -&gt; value = ( uint8_t ) * string;
 it -&gt; next -&gt; next = 0;
 }

 return head.next;
}

void free_list ( list_t* list )
{
 for ( list_t* it = list; it != 0; ) {
 list_t* next = it -&gt; next;
 free ( it );
 it = next;
 }
}

void print_list ( list_t* list )
{
 printf ( "[ " );

 if ( list ) {
 printf ( "%c", list -&gt; value );

 for ( list_t* it = list -&gt; next; it != 0; it = it -&gt; next )
 printf ( ", %c", it -&gt; value );
 }

 printf ( " ]\n" );
}


int main ( int nargs, char** args )
{
 list_t* list = make_list ( nargs &gt; 1 ? args[1] : "wibble" );


 print_list ( list );

 list_t* sorted = sort_list ( list );


 print_list ( sorted );

 free_list ( list );
}
</code></pre>

blocks|key|1438168|text|比较排序(即基于比较元素的排序)不可能比n+log+n快。底层数据结构是什么并不重要。参见Wikipedia。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1438169|其他类型的排序利用列表中有许多相同的元素(例如计数排序)，或者列表中元素的一些预期分布，速度更快，尽管我想不出任何在链表上工作得特别好的排序。|1438170|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Comparison_sort^0|K|7|19|9|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]]|D|@$9|S|A|T|1|U]]|E|$]]|$1|F|3|G|5|6|7|V|8|@]|D|@]|E|$]]|$1|H|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]]]

Comparison sorts (i.e. ones based on comparing elements) cannot possibly be faster than <code>n log n</code>. It doesn't matter what the underlying data structure is. See <a href="http://en.wikipedia.org/wiki/Comparison_sort" rel="noreferrer">Wikipedia</a>.

Other kinds of sort that take advantage of there being lots of identical elements in the list (such as the counting sort), or some expected distribution of elements in the list, are faster, though I can't think of any that work particularly well on a linked list.

blocks|key|1438274|text|正如多次提到的，对一般数据进行基于比较的排序的下限将是O(n+log+n)。简单地总结一下这些论点，有n！列表可以以不同的方式排序。任何类型的比较树，具有n！(在O(n%5En)中)可能的最终排序至少需要log(n!)作为它的高度:这给出了一个O(+log+(n%5E+n)+)的下界，即O(n+Log+N)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1438275|因此，对于链表上的一般数据，对任何可以比较两个对象的数据的最佳排序将是O(n+log+n)。然而，如果你有一个更有限的工作领域，你可以改善它所需的时间(至少与n成比例)。例如，如果您正在处理不大于某个值的整数，您可以使用Counting+Sort或Radix+Sort，因为这些对象使用您要排序的特定对象来降低复杂度，并与n成比例。但是，请注意，这会增加一些您可能没有考虑到的复杂性(例如，计数排序和基数排序都会添加基于要排序的数字大小的因子，例如，O(n%2Bk)，其中k是计数排序的最大数的大小)。|offset|length|1438276|此外，如果您碰巧有一个完美散列的对象(或者至少有一个以不同方式映射所有值的散列)，您可以尝试对它们的散列函数使用计数或基数排序。|1438277|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Counting_sort|1|http://en.wikipedia.org/wiki/Radix_sort^0|0|32|D|0|3G|A|1|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]|$D|W|E|X|1|Y]]|A|$]]|$1|F|3|G|5|6|7|Z|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

As stated many times, the lower bound on comparison based sorting for general data is going to be O(n log n). To briefly resummarize these arguments, there are n! different ways a list can be sorted. Any sort of comparison tree that has n! (which is in O(n^n)) possible final sorts is going to need at least log(n!) as its height: this gives you a O(log(n^n)) lower bound, which is O(n log n). 

So, for general data on a linked list, the best possible sort that will work on any data that can compare two objects is going to be O(n log n). However, if you have a more limited domain of things to work in, you can improve the time it takes (at least proportional to n). For instance, if you are working with integers no larger than some value, you could use <a href="http://en.wikipedia.org/wiki/Counting_sort" rel="noreferrer">Counting Sort</a> or <a href="http://en.wikipedia.org/wiki/Radix_sort" rel="noreferrer">Radix Sort</a>, as these use the specific objects you're sorting to reduce the complexity with proportion to n. Be careful, though, these add some other things to the complexity that you may not consider (for instance, Counting Sort and Radix sort both add in factors that are based on the size of the numbers you're sorting, O(n+k) where k is the size of largest number for Counting Sort, for instance).

Also, if you happen to have objects that have a perfect hash (or at least a hash that maps all values differently), you could try using a counting or radix sort on their hash functions.

blocks|key|1223628|text|Radix+sort特别适合于链表，因为可以很容易地制作对应于每个可能的数字值的头指针的表。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1223629|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Radix_sort^0|0|A|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

A <a href="http://en.wikipedia.org/wiki/Radix_sort" rel="nofollow noreferrer">Radix sort</a> is particularly suited to a linked list, since it's easy to make a table of head pointers corresponding to each possible value of a digit.

blocks|key|1223735|text|这是一篇关于这个主题的很好的小论文。他的经验结论是Treesort是最好的，其次是Quicksort和Mergesort。沉淀物排序、冒泡排序、选择排序的性能非常差。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1223736|Ching-Kuang+Shene链表排序算法的比较研究|1223737|http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981|offset|length|1223738|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|0|1R|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Q|8|@]|9|@$F|R|G|S|1|T]]|A|$]]|$1|H|3|-4|5|6|7|U|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|E]]]]

This is a nice little paper on this topic. His empirical conclusion is that Treesort is best, followed by Quicksort and Mergesort. Sediment sort, bubble sort, selection sort perform very badly.

A COMPARATIVE STUDY OF LINKED LIST SORTING ALGORITHMS
by Ching-Kuang Shene

<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981" rel="noreferrer">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981</a>

blocks|key|1438579|text|Here's+an+implementation只遍历列表一次，收集运行，然后以与mergesort相同的方式调度合并。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1438580|复杂度为O(n+)，其中n是项数，m是运行次数。最好的情况是O(n)+(如果数据已经排序)，最坏的情况是O(n+log+n)，正如预期的那样。|1438581|它需要O(log+)临时内存；排序在列表中就地完成。|1438582|(更新如下。评论者1提出了一个很好的观点，我应该在这里描述它)|1438583|算法的要点是：|1438584|++++while+list+not+empty
++++++++accumulate+a+run+from+the+start+of+the+list
++++++++merge+the+run+with+a+stack+of+merges+that+simulate+mergesort's+recursion
++++merge+all+remaining+items+on+the+stack|code-block|syntax|javascript|1438585|累积运行不需要太多的解释，但利用机会同时积累上升运行和下降运行(反向)是很好的。在这里，它将小于运行头部的项放在前面，并附加大于或等于运行结束的项。(请注意，前置应使用strict+less-than以保持排序稳定性。)|1438586|最简单的方法就是将合并代码粘贴到这里：|1438587|++++int+i+=+0;
++++for+(+;+i+<+stack.size();+%2B%2Bi)+{
++++++++if+(!stack[i])
++++++++++++break;
++++++++run+=+merge(run,+stack[i],+comp);
++++++++stack[i]+=+nullptr;
++++}
++++if+(i+<+stack.size())+{
++++++++stack[i]+=+run;
++++}+else+{
++++++++stack.push_back(run);
++++}|1438588|考虑对列表进行排序(d+A+G+I+B+E+C+F+J+h)+(忽略运行)。堆栈状态的处理方式如下：|1438589|++++[+]
++++[+(d)+]
++++[+()+(a+d)+]
++++[+(g),+(a+d)+]
++++[+()+()+(a+d+g+i)+]
++++[+(b)+()+(a+d+g+i)+]
++++[+()+(b+e)+(a+d+g+i)+]
++++[+(c)+(b+e)+(a+d+g+i+)+]
++++[+()+()+()+(a+b+c+d+e+f+g+i)+]
++++[+(j)+()+()+(a+b+c+d+e+f+g+i)+]
++++[+()+(h+j)+()+(a+b+c+d+e+f+g+i)+]|1438590|然后，最后，合并所有这些列表。|1438591|请注意，堆栈i上的项目(运行)数量要么为0，要么为2%5Ei，堆栈大小由1%2Blog2(Nrun)限制。每个元素在每个堆栈级别被合并一次，因此O(n+)个比较。这里有一个与Timsort的相似之处，尽管Timsort使用类似斐波那契序列的东西来维护它的堆栈，其中它使用2的幂。|1438592|累积运行利用了任何已排序的数据，因此对于已排序的列表(一次运行)，最佳情况下的复杂度为O(n)。由于我们同时累加升序和降序运行，因此运行的长度将始终至少为2。(这将使最大堆栈深度至少减少1，从而首先支付查找运行的成本。)对于高度随机化的数据，最坏情况下的复杂度为O(n+log+n)，正如预期的那样。|1438593|(嗯.第二次更新。)|1438594|或者直接在bottom-up+mergesort上看维基百科。|1438595|entityMap|0|LINK|mutability|MUTABLE|url|https://gist.github.com/sjswitzer/1dc76dc0b4dcf67a7fef|1|https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists^0|0|O|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|5|J|1|0^^$0|@$1|2|3|4|5|6|7|1K|8|@]|9|@$A|1L|B|1M|1|1N]]|C|$]]|$1|D|3|E|5|6|7|1O|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|1P|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|1Q|8|@]|9|@]|C|$]]|$1|J|3|K|5|6|7|1R|8|@]|9|@]|C|$]]|$1|L|3|M|5|N|7|1S|8|@]|9|@]|C|$O|P]]|$1|Q|3|R|5|6|7|1T|8|@]|9|@]|C|$]]|$1|S|3|T|5|6|7|1U|8|@]|9|@]|C|$]]|$1|U|3|V|5|N|7|1V|8|@]|9|@]|C|$O|P]]|$1|W|3|X|5|6|7|1W|8|@]|9|@]|C|$]]|$1|Y|3|Z|5|N|7|1X|8|@]|9|@]|C|$O|P]]|$1|10|3|11|5|6|7|1Y|8|@]|9|@]|C|$]]|$1|12|3|13|5|6|7|1Z|8|@]|9|@]|C|$]]|$1|14|3|15|5|6|7|20|8|@]|9|@]|C|$]]|$1|16|3|17|5|6|7|21|8|@]|9|@]|C|$]]|$1|18|3|19|5|6|7|22|8|@]|9|@$A|23|B|24|1|25]]|C|$]]|$1|1A|3|-4|5|6|7|26|8|@]|9|@]|C|$]]]|1B|$1C|$5|1D|1E|1F|C|$1G|1H]]|1I|$5|1D|1E|1F|C|$1G|1J]]]]

<a href="https://gist.github.com/sjswitzer/1dc76dc0b4dcf67a7fef" rel="nofollow">Here's an implementation</a> that traverses the list just once, collecting runs, then schedules the merges in the same way that mergesort does.

Complexity is O(n log m) where n is the number of items and m is the number of runs. Best case is O(n) (if the data is already sorted) and worst case is O(n log n) as expected.

It requires O(log m) temporary memory; the sort is done in-place on the lists.

(updated below. commenter one makes a good point that I should describe it here)

The gist of the algorithm is:

<pre><code> while list not empty
 accumulate a run from the start of the list
 merge the run with a stack of merges that simulate mergesort's recursion
 merge all remaining items on the stack
</code></pre>

Accumulating runs doesn't require much explanation, but it's good to take the opportunity to accumulate both ascending runs and descending runs (reversed). Here it prepends items smaller than the head of the run and appends items greater than or equal to the end of the run. (Note that prepending should use strict less-than to preserve sort stability.)

It's easiest to just paste the merging code here:

<pre><code> int i = 0;
 for ( ; i &lt; stack.size(); ++i) {
 if (!stack[i])
 break;
 run = merge(run, stack[i], comp);
 stack[i] = nullptr;
 }
 if (i &lt; stack.size()) {
 stack[i] = run;
 } else {
 stack.push_back(run);
 }
</code></pre>

Consider sorting the list (d a g i b e c f j h) (ignoring runs). The stack states proceed as follows:

<pre><code> [ ]
 [ (d) ]
 [ () (a d) ]
 [ (g), (a d) ]
 [ () () (a d g i) ]
 [ (b) () (a d g i) ]
 [ () (b e) (a d g i) ]
 [ (c) (b e) (a d g i ) ]
 [ () () () (a b c d e f g i) ]
 [ (j) () () (a b c d e f g i) ]
 [ () (h j) () (a b c d e f g i) ]
</code></pre>

Then, finally, merge all these lists.

Note that the number of items (runs) at stack[i] is either zero or 2^i and the stack size is bounded by 1+log2(nruns). Each element is merged once per stack level, hence O(n log m) comparisons. There's a passing similarity to Timsort here, though Timsort maintains its stack using something like a Fibonacci sequence where this uses powers of two.

Accumulating runs takes advantage of any already sorted data so that best case complexity is O(n) for an already sorted list (one run). Since we're accumulating both ascending and descending runs, runs will always be at least length 2. (This reduces the maximum stack depth by at least one, paying for the cost of finding the runs in the first place.) Worst case complexity is O(n log n), as expected, for data that is highly randomized.

(Um... Second update.)

Or just see wikipedia on <a href="https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists" rel="nofollow">bottom-up mergesort</a>.

blocks|key|1438680|text|问题出在LeetCode+#148，所有主流语言都提供了大量的解决方案。我的方法如下所示，但我想知道时间复杂度。为了找到中间的元素，我们每次都会遍历完整的列表。第一次迭代n元素，第二次迭代2+*+n/2元素，以此类推。似乎是O(n%5E2)的时候了。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1438681|def+sort(linked_list:+LinkedList[int])+->+LinkedList[int]:
++++#+Return+n+//+2+element
++++def+middle(head:+LinkedList[int])+->+LinkedList[int]:
++++++++if+not+head+or+not+head.next:
++++++++++++return+head
++++++++slow+=+head
++++++++fast+=+head.next

++++++++while+fast+and+fast.next:
++++++++++++slow+=+slow.next
++++++++++++fast+=+fast.next.next

++++++++return+slow

++++def+merge(head1:+LinkedList[int],+head2:+LinkedList[int])+->+LinkedList[int]:
++++++++p1+=+head1
++++++++p2+=+head2
++++++++prev+=+head+=+None

++++++++while+p1+and+p2:
++++++++++++smaller+=+p1+if+p1.val+<+p2.val+else+p2
++++++++++++if+not+head:
++++++++++++++++head+=+smaller
++++++++++++if+prev:
++++++++++++++++prev.next+=+smaller
++++++++++++prev+=+smaller

++++++++++++if+smaller+==+p1:
++++++++++++++++p1+=+p1.next
++++++++++++else:
++++++++++++++++p2+=+p2.next

++++++++if+prev:
++++++++++++prev.next+=+p1+or+p2
++++++++else:
++++++++++++head+=+p1+or+p2

++++++++return+head

++++def+merge_sort(head:+LinkedList[int])+->+LinkedList[int]:
++++++++if+head+and+head.next:
++++++++++++mid+=+middle(head)
++++++++++++mid_next+=+mid.next
++++++++++++#+Makes+it+easier+to+stop
++++++++++++mid.next+=+None

++++++++++++return+merge(merge_sort(head),+merge_sort(mid_next))
++++++++else:
++++++++++++return+head

++++return+merge_sort(linked_list)|code-block|syntax|javascript|1438682|entityMap|0|LINK|mutability|MUTABLE|url|https://leetcode.com/problems/sort-list/^0|2D|1|2M|7|34|6|4|D|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]]|D|@$9|Z|A|10|1|11]]|E|$]]|$1|F|3|G|5|H|7|12|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|13|8|@]|D|@]|E|$]]]|L|$M|$5|N|O|P|E|$Q|R]]]]

The question is <a href="https://leetcode.com/problems/sort-list/" rel="nofollow noreferrer">LeetCode #148</a>, and there are plenty of solutions offered in all major languages. Mine is as follows, but I'm wondering about the time complexity. In order to find the middle element, we traverse the complete list each time. First time <code>n</code> elements are iterated over, second time <code>2 * n/2</code> elements are iterated over, so on and so forth. It seems to be <code>O(n^2)</code> time.
<pre><code>def sort(linked_list: LinkedList[int]) -&gt; LinkedList[int]:
 # Return n // 2 element
 def middle(head: LinkedList[int]) -&gt; LinkedList[int]:
 if not head or not head.next:
 return head
 slow = head
 fast = head.next

 while fast and fast.next:
 slow = slow.next
 fast = fast.next.next

 return slow

 def merge(head1: LinkedList[int], head2: LinkedList[int]) -&gt; LinkedList[int]:
 p1 = head1
 p2 = head2
 prev = head = None

 while p1 and p2:
 smaller = p1 if p1.val &lt; p2.val else p2
 if not head:
 head = smaller
 if prev:
 prev.next = smaller
 prev = smaller

 if smaller == p1:
 p1 = p1.next
 else:
 p2 = p2.next

 if prev:
 prev.next = p1 or p2
 else:
 head = p1 or p2

 return head

 def merge_sort(head: LinkedList[int]) -&gt; LinkedList[int]:
 if head and head.next:
 mid = middle(head)
 mid_next = mid.next
 # Makes it easier to stop
 mid.next = None

 return merge(merge_sort(head), merge_sort(mid_next))
 else:
 return head

 return merge_sort(linked_list)
</code></pre>

I'm curious if O(n log n) is the best a linked list can do.

What's the fastest algorithm for sorting a linked list?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我很好奇O(n log n)是否是链表所能做到的最好的。

问链表排序的最快算法是什么？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问链表排序的最快算法是什么？EN