关于算法：合并排序链接列表

Merge Sort a Linked List

我最近刷了一些基础知识，发现合并排序链表是一个非常好的挑战。如果你有一个很好的实现，那么在这里展示它。

不知道为什么它应该是一个很大的挑战，因为它在这里说，这是一个简单的Java实现，没有任何"聪明的技巧"。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

//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;
}

更简单/更清晰的实现可能是递归实现，NLog(N)执行时间更清晰。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

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;
}

注意：这具有递归的Log(N)存储要求。绩效应与我发布的其他策略大致相当。这里有一个潜在的优化，通过运行合并循环while(list && right)，并简单地附加剩余列表(因为我们并不真正关心列表的结尾;知道它们合并就足够了)。

非常基于以下优秀代码：http：//www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

略微整理，整理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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;
}

注意：这是O(NLog(N))保证，并使用O(1)资源(没有递归，没有堆栈，没有)。

一种有趣的方法是维护一个堆栈，只有当堆栈上的列表具有相同数量的元素时才合并，否则推送列表，直到输入列表中的元素用完为止，然后合并堆栈。

我一直在为这个算法优化杂乱而着迷，下面是我最终得到的结果。 Internet和StackOverflow上的很多其他代码都非常糟糕。有人试图获得列表的中间点，进行递归，为剩余节点设置多个循环，保持大量事物的数量 - 所有这些都是不必要的。 MergeSort自然适合链表，算法可以很漂亮和紧凑，但达到那个状态并不容易。

根据我所知，下面的代码保持最小数量的变量，并具有算法所需的最小逻辑步骤数(即，不使代码不可维护/不可读)。但是我没有尝试最小化LOC并保留尽可能多的空白以保持可读性。我通过相当严格的单元测试测试了这段代码。

请注意，此答案结合了其他答案https://stackoverflow.com/a/3032462/207661中的一些技巧。虽然代码在C＃中，但转换为C ++，Java等应该是微不足道的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

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循环平均每次迭代评估3个表达式，我认为这是最小值。

更新：@ ideasman42已将上述代码翻译为C / C ++以及修复注释和更多改进的建议。上面的代码现在是最新的。

最简单的是
Gonnet + Baeza Yates算法手册。你用你想要的排序元素的数量来调用它，它递归地被一分为二，直到它达到一个大小一个列表的请求，然后你只需剥离原始列表的前面。这些都被合并到一个完整大小的排序列表。

[请注意，第一篇文章中基于酷堆栈的文章称为在线合并，它在Knuth Vol 3的练习中得到了最小的提及]

这是另一种递归版本。这不需要沿着列表进行拆分：我们提供一个指向head元素的指针(不是排序的一部分)和一个长度，递归函数返回一个指向排序列表末尾的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
}
}
}

我决定在这里测试一些例子，还有一个方法，最初是由Jonathan Cunningham在Pop-11中编写的。我用C＃编写了所有方法，并与一系列不同的列表大小进行了比较。我比较了Raja R Harinath的Mono eglib方法，Shital Shah的C＃代码，Jayadev的Java方法，David Gamble的递归和非递归版本，Ed Wynn的第一个C代码(这与我的样本数据集崩溃，我没有调试)和Cunningham的版本。完整代码：https：//gist.github.com/314e572808f29adb0e41.git。

Mono eglib基于与Cunningham类似的想法并具有相似的速度，除非列表恰好已经排序，在这种情况下Cunningham的方法要快得多(如果它的部分排序，eglib稍快一些)。 eglib代码使用固定表来保持合并排序递归，而Cunningham的方法通过使用递增的递归级别来工作 - 所以它开始不使用递归，然后是1-deep递归，然后是2-deep recursion，依此类推，排序需要多少步骤。我发现Cunningham代码更容易理解，并且没有猜测参与递归表有多大，所以它得到了我的投票。我在这个页面尝试的其他方法慢了两倍或更多。

这是Pop-11排序的C＃端口：

/// <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;
}
}

链接列表的非递归合并排序的另一个示例，其中函数不是类的一部分。此示例代码和HP / Microsoft std :: list :: sort都使用相同的基本算法。自下而上的非递归合并排序，使用指向列表的第一个节点的小(26到32)指针数组，其中array [i]为0或指向大小为2的列表。在我的系统Intel 2600K 3.4ghz上，它可以在大约1秒内将具有32位无符号整数的400万个节点分类为数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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;
}

这是我对Knuth的"列表合并排序"的实现(来自TAOCP第3卷的算法5.2.4L，第2版)。我最后会添加一些评论，但这是一个总结：

在随机输入上，它比Simon Tatham的代码运行得快一点(参见Dave Gamble的非递归答案，带链接)但比Dave Gamble的递归代码慢一点。它比任何一个都难以理解。至少在我的实现中，它要求每个元素都有两个指向元素的指针。 (另一种选择是一个指针和一个布尔标志。)因此，它可能不是一个有用的方法。然而，一个显着的点是，如果输入具有已经排序的长延伸，则它运行得非常快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

element *knuthsort(element *list)
{ /* This is my attempt at implementing Knuth's 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;
}

单声道eglib中有一个非递归链表合并。

基本思想是各种合并的控制循环与二进制整数的按位增量平行。存在O(n)合并以将n个节点"插入"到合并树中，并且这些合并的等级对应于递增的二进制数字。使用此类比，只需要将合并树的O(log n)节点实现为临时保持数组。

最简单的Java实现：

Time Complexity: O(nLogn) n = number of nodes. Each iteration through the linked list doubles the size of the sorted smaller linked lists. For example, after the first iteration, the linked list will be sorted into two halves. After the second iteration, the linked list will be sorted into four halves. It will keep sorting up to the size of the linked list. This will take O(logn) doublings of the small linked lists' sizes to reach the original linked list size. The n in nlogn is there because each iteration of the linked list will take time proportional to the number of nodes in the originial linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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;
}

}

这是整段代码，它显示了我们如何在java中创建链接列表并使用Merge排序对其进行排序。我在MergeNode类中创建节点，还有另一个类MergesortLinklist，其中有除法和合并逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229

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;
}
}

}

我没有看到这里发布的任何C ++解决方案。所以，在这里。希望它可以帮助某人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

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;
}
};

以下是链接列表上的合并排序的Java实现：

Time Complexity: O(n.logn)

Space Complexity: O(1) - Merge sort implementation on Linked List avoids the O(n) auxiliary storage cost normally associated with the
algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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;
}
}

基于最高投票答案的经过测试的，工作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中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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;
}