Merge Sort linked list

Question

I recently learned some basics and found that merging sorted linked list is a pretty good problem. If you have a good implementation then show it here.

Answer 1

I wonder why this should be a big problem, as stated here, here is a simple implementation in Java without any “tricky tricks”.

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

Answer 2

A simpler / clearer implementation may be a recursive implementation, from which the NLog (N) runtime is more understandable.

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

Note. For recursion, this is a requirement to store a log (N). Performance should be roughly comparable to another strategy that I posted. There is potential optimization here by starting the while (list && right) merge cycle and simply adding the remaining list (since we don't really care about the end of the lists, knowing that they are combined enough).

Answer 3

Heavily based on EXCELLENT code: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Slightly processed and tidied up:

 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: this is O (NLog (N)) guaranteed and uses O (1) resources (no recursion, no stack, nothing).

Answer 4

One interesting way is to maintain the stack and merge only if the list has the same number of items in the stack, and otherwise click the list until you finish the items in the incoming list, and then merge the stack.

Answer 5

The easiest of the Gonnet + Baeza Yates Algorithm Reference . You call it with the number of sorted items you want that are recursively halved until it reaches the query for a list of size one, which you then simply clear before the original list. All of them are combined into a full-sized sorted list.

[Note that the stack-based class in the first column is called an online network and it gets the smallest mention in an exercise in Knuth Vol 3]

Answer 6

Here's an alternative recursive version. You don’t have to do this according to the list in order to separate it: we supply a pointer to the head element (which is not part of the sort) and length, and a recursive function returns a pointer to the end of the sorted list.

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

Answer 7

I was obsessed with optimizing the clutter for this algorithm, and below is what I finally came to. Lots of other code on the web and Stackoverflow is terribly bad. There are people trying to get the middle point of the list, doing recursion, having several loops for the remaining nodes, supporting calculations of a ton of things - ALL of this is not necessary. MergeSort is naturally suitable for a linked list, and the algorithm can be nice and compact, but it is not easy to get to that state.

Below the code supports the minimum number of variables and has the minimum number of logical steps necessary for the algorithm (i.e. without making the code unreachable / unreadable), as far as I know. However, I did not try to minimize LOC and kept as much free space as needed to maintain readability. I tested this code through fairly rigorous unit tests.

Please note that this answer combines several methods from another answer https://stackoverflow.com/a/464632/ Although the code is in C #, it should be trivial to convert to C ++, Java, etc.

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

sights

• There is no special handling for cases such as list 0 from list 1, etc. These cases "just work."
• Many "standard" algorithms have two loops to pass through the remaining elements in order to handle the case when one list is shorter than the other. The above code eliminates the need for it.
• We are sure that the sorting is stable.
• The inner while loop, which is a hot spot, evaluates on average three expressions per iteration, which I think are minimal.

Update: @ ideasman42 has the C / C ++ code translated above , as well as suggestions for fixing comments and even greater improvement. The above code is now updated with this data.

Answer 8

I decided to check out the examples here, as well as another approach originally written by Jonathan Cunningham in Pop-11. I encoded all the approaches in C # and made a comparison with different sizes of lists. I compared the Mono eglib approach from Raja R Harinath, the C # code from Shital Shah, the Java Jayadev approach, the recursive and non-recursive versions of David Gamble, the first C code from Ed Wynn (this crashed with my sample dataset, I did not debug it), and the version Cunningham. The full code is here: https://gist.github.com/314e572808f29adb0e41.git .

Mono eglib is based on a similar idea for Cunningham and has comparable speed, unless the list is sorted already, in which case Cunningham's approach is much faster (if partially sorted, eglib is a little faster). The eglib code uses a fixed table to store merge sort recursion, while Cunningham's approach works using increasing levels of recursion - so it starts without recursion, then with 1st recursion, then with 2-depth recursion, etc. According to how many steps are required for sorting. I find Cunningham's code a little easier to follow, and there is no guesswork regarding how big the recursion table is, so it gets my vote. Other approaches that I tried on this page were two or more times slower.

Here is the C # port for sorting 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; } } 

Answer 9

Here's my Knuth implementation of “List Merge Sort” (Algorithm 5.2.4L from Vol.3 TAOCP, 2nd ed.). I will add a few comments at the end, but here's a summary:

On random login, it runs a little faster than the Simon Tatham code (see Dave Gamble's non-recursive answer with a link), but slightly slower than the Dave Gamble recursive code. This is harder to understand than any other. At least in my implementation, each element should have two pointers to the elements. (An alternative could be a single pointer and a boolean flag.) So this is probably not a very useful approach. However, one distinguishing point is that it works very fast if the input has long segments that are already sorted.

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

Answer 10

There is a non-recursive merged merge list in mono eglib .

The basic idea is that the control loop for the various associations is parallel to the bitwise increment of the binary integer. O (n) merges with the "insertion" of n nodes into the merge tree, and the rank of these merges corresponds to a binary digit, which increases. Using this analogy, you only need to materialize only the O (log n) nodes of the merge tree into a temporary storage array.

Answer 11

Another example of non-recursive merge sorting for linked lists, where functions are not part of the class. This code sample and HP / Microsoft std :: list :: sort use the same basic algorithm. A low, non-recursive merge sort that uses a small (26 to 32) array of pointers to the first nodes of the list, where array [i] is either 0 or points to a list of size 2 for power i. In my Intel 2600K 3.4ghz system can sort 4 million nodes with 32-bit unsigned integers as data in about 1 second.

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

Answer 12

This is the whole piece of code that shows how we can create a list of links in java and sort it using Merge sort. I create a node in the MergeNode class, and there is another MergesortLinklist class where there is a split and merge logic.

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

Answer 13

I do not see any C ++ solutions posted here. So that’s it. Hope this helps someone.

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

Answer 14

Here is the Java implementation of merge sort in a linked list:

• Difficulty of time: O (n.logn)
• Space complexity: O (1) - implementation of merge sort in a linked list avoids the cost of auxiliary storage O (n), usually associated with the algorithm

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

Answer 15

Proven working C++ version of a single linked list based on the answer with the most votes .

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

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

Answer 17

You can use this merge sort implementation and write your own functions to interact with the linked list, as if it were an array.

Answer 18

One of the drawbacks of merge sorting is that it uses O (n) space to store data. those.when combining two subscriptions for a linked list, this can be avoided by continuing to change the next pointer in the node list. The latter implementation seems neat, but does not take it into account.

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