合并排序链接列表

想知道为什么它应该是一个巨大的挑战,正如这里所说的,这里是一个简单的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; 
        }
        
    }
    dummyHead.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)的执行时间。

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

主要基于以下优秀代码: 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;
}

一个有趣的方法是维护一个堆栈,并且只有当堆栈上的列表具有相同数量的元素时才进行合并,否则将推送该列表,直到传入列表中的元素用完,然后向上合并堆栈。

最简单的是 Gonnet + Baeza Yates Handbook of Algorithms . 你用你想要的排序元素的数量来调用它,递归地将它平分,直到它达到一个大小为1的列表的请求,然后你只需从原始列表的前面剥离。这些都被合并成一个完整的排序列表。

[请注意,第一篇文章中基于cool stack的一个叫做Online Mergesort,在Knuth Vol 3的一个练习中它得到的提及最少]

这是另一个递归版本。这不需要单步执行列表来拆分它:我们提供一个指向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;
    }
  }
}

我一直在为这个算法优化杂波而困扰,下面是我最终得出的结论。互联网上的许多其他代码和StackOverflow是非常糟糕的。有人试图得到列表的中间点,进行递归,对剩余节点有多个循环,维护大量的东西——所有这些都是不必要的。MergeSort自然适合于链表,算法可以是漂亮和紧凑的,但要达到这种状态并不容易。

注意这个答案结合了其他答案的一些技巧 https://stackoverflow.com/a/3032462/207661 . 当代码在C语言中时,将其转换为C++、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循环是一个热点,平均每个迭代计算3个表达式,我认为这是一个可以做到的最小值。

translated above code to C/C++ 以及对修改意见和更多改进的建议。以上代码现在是最新的这些。

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

Mono-eglib基于与Cunningham相似的思想,并且速度相当,除非列表碰巧已经排序,在这种情况下,Cunningham的方法要快得多(如果部分排序,eglib稍微快一点)。eglib代码使用一个固定的表来保存merge sort递归,而Cunningham的方法是通过使用不断增加的递归级别来工作的,因此它一开始不使用递归,然后使用1-deep递归,然后使用2-deep递归,依此类推,这取决于执行排序所需的步骤数。我发现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;
    }
}

这是我对Knuth的“列表合并排序”的实现(算法5.2.4L,摘自TAOCP第3卷,第2版)。我将在结尾处添加一些评论,但下面是一个总结:

在随机输入上,它比Simon Tatham的代码运行得快一点(见Dave Gamble的非递归答案,带有链接),但比Dave Gamble的递归代码运行得慢一点。这比这两者都难理解。至少在我的实现中,它要求每个元素有两个指向元素的指针。(另一种选择是一个指针和一个布尔标志)所以,这可能不是一个有用的方法。但是,有一点很特别,如果输入的数据段很长,并且已经排序,那么它的运行速度非常快。

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

这里有一个非递归链表mergesort mono eglib .

其基本思想是各种合并的控制循环与二进制整数的按位递增并行。有 O(n) 合并到“插入” n 合并树中的节点,这些合并的秩对应于递增的二进制数字。用这个比喻,只有 O(对数n) 合并树的节点需要具体化为一个临时保持数组。

C++ 单链表的版本, 根据最高票数的答案 .

单链接列表.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;
            }

        }

    };
}

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

链表的非递归合并排序的另一个示例,其中函数不是类的一部分。此示例代码和HP/Microsoft std::list::sort 两者使用相同的基本算法。一种自下而上的非递归合并排序,它使用一个小的(26到32)指针数组指向列表的第一个节点,其中 array[i]

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

Visual Studio 2015已更改 标准::列表::排序 将基于迭代器而不是列表,还更改为自顶向下的合并排序,这需要扫描的开销。我最初假设使用迭代器需要切换到top-down,但是当再次被问及这个问题时,我对此进行了研究并确定不需要切换到较慢的top-down方法,并且可以使用相同的基于迭代器的逻辑实现bottom-up。此链接中的答案解释了这一点,并提供了一个独立的示例以及VS2019的替代品 std::list::sort() 在include文件“list”中。

`std::list<>::sort()` - why the sudden switch to top-down strategy?

这段代码展示了如何用java创建linklist并使用Merge sort对其进行排序。我在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;
        }
    }

}

我没有看到任何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;
    }
};

以下是链表合并排序的Java实现:

• 时间复杂度:O(n.logn)
• 空间复杂性:O(1)-链表上的合并排序实现避免了通常与 算法

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

时间复杂度:O(nLogn)n=节点数。通过链表的每次迭代都会使已排序的较小链表的大小加倍。例如,在第一次迭代之后,链表将被分为两半。在第二次迭代之后,链表将被分为四部分。它将继续按链接列表的大小排序。这将需要O(logn)加倍小链接列表的大小,以达到原始链接列表的大小。nlogn中的n是存在的,因为链表的每次迭代将花费与原始链表中的节点数成比例的时间。

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

}

嘿,我知道这个答案有点晚了,但是得到了一个简单的答案。

代码是F#的,但可以用任何语言。由于这是ML家族的一种不常见的语言,我将给出一些增强可读性的要点。

// split the list into a singleton list
let split list = List.map (fun x -> [x]) lst

// takes to list and merge them into a sorted list
let sort lst1 lst2 =
   // nested function to hide accumulator
   let rec s acc pair =
       match pair with
       // empty list case, return the sorted list
       | [], [] -> List.rev acc
       | xs, [] | [], xs ->
          // one empty list case, 
          // append the rest of xs onto acc and return the sorted list
          List.fold (fun ys y -> y :: ys) acc xs
          |> List.rev
       // general case
       | x::xs, y::ys ->
          match x < y with
          | true -> // cons x onto the accumulator
              s (x::acc) (xs,y::ys)
          | _ ->
              // cons y onto the accumulator
              s (y::acc) (x::xs,ys)

    s [] (lst1, lst2)  

let msort lst =
  let rec merge acc lst =
      match lst with
      | [] ->
          match acc with
          | [] -> [] // empty list case
          | _ -> merge [] acc
      | x :: [] -> // single list case (x is a list)
         match acc with
         | [] -> x // since acc are empty there are only x left, hence x are the sorted list.
         | _ -> merge [] (x::acc) // still need merging.
       | x1 :: x2 :: xs ->
           // merge the lists x1 and x2 and add them to the acummulator. recursiv call
           merge (sort x1 x2 :: acc) xs

   // return part
   split list // expand to singleton list list
   |> merge [] // merge and sort recursively.

需要注意的是,这是完全尾部递归的,因此不存在堆栈溢出的可能性,并且通过先将列表一次性扩展为单例列表,我们可以降低最坏成本的常数因子。因为merge是在list-of-list上工作的,所以我们可以递归地合并和排序内部列表,直到到达一个固定点,所有的内部列表都被排序到一个列表中,然后返回该列表,从而再次从列表列表折叠到列表。

下面是使用 Swift程序设计语言 .

//Main MergeSort Function
func mergeSort(head: Node?) -> Node? {
   guard let head = head else { return nil }
   guard let _ = head.next else { return head }

   let middle = getMiddle(head: head)
   let left = head
   let right = middle.next

   middle.next = nil

   return merge(left: mergeSort(head: left), right: mergeSort(head: right))
}

//Merge Function
func merge(left: Node?, right: Node?) -> Node? {

   guard let left = left, let right = right else { return nil}

   let dummyHead: Node = Node(value: 0)

   var current: Node? = dummyHead
   var currentLeft: Node? = left
   var currentRight: Node? = right

   while currentLeft != nil && currentRight != nil {
       if currentLeft!.value < currentRight!.value {
        current?.next = currentLeft
        currentLeft = currentLeft!.next
       } else {
        current?.next = currentRight
        currentRight = currentRight!.next
       }
       current = current?.next
   }


   if currentLeft != nil {
        current?.next = currentLeft
   }

   if currentRight != nil {
        current?.next = currentRight
   }

   return dummyHead.next!
}

这是 节点类 &安培; getMiddle方法

class Node { 
    //Node Class which takes Integers as value
    var value: Int
    var next: Node?
    
    init(value: Int) {
        self.value = value
    }
}

func getMiddle(head: Node) -> Node {
    guard let nextNode = head.next else { return head }
    
    var slow: Node = head
    var fast: Node? = head
    
    while fast?.next?.next != nil {
        slow = slow.next!
        fast = fast!.next?.next
    }
    
    
    return slow
}

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