合并排序链表

在mono eglib中有一个非递归的链表归并排序。

基本思路是各种合并的控制循环与二进制整数的按位增量相平行。有O(n)次合并将n个节点“插入”到归并树中，这些合并的等级对应于递增的二进制位。使用这个类比，只需要将归并树的O(log n)个节点实体化为临时保持数组。

这是我实现的Knuth的“列表归并排序”（TAOCP第3卷第2版算法5.2.4L）。我会在末尾添加一些注释，但这是一个摘要：

在随机输入上，它比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;
}

最简单的Java实现：

时间复杂度：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;
    }

}

我这里没有看到任何关于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) - 链表上的归并排序实现避免了通常与该算法相关的O(n)辅助存储成本

class Solution
{
    public ListNode mergeSortList(ListNode head) 
    {
        if(head == null || head.next == null)
            return head;

        ListNode mid = getMid(head), second_head = mid.next; mid.next = null;

        return merge(mergeSortList(head), mergeSortList(second_head));
    }

    private ListNode merge(ListNode head1, ListNode head2)
    {
        ListNode result = new ListNode(0), current = result;

        while(head1 != null && head2 != null)
        {
            if(head1.val < head2.val)
            {
                current.next = head1;
                head1 = head1.next;
            }
            else
            {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }

        if(head1 != null) current.next = head1;
        if(head2 != null) current.next = head2;

        return result.next;
    }

    private ListNode getMid(ListNode head)
    {
        ListNode slow = head, fast = head.next;

        while(fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

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

这里是 Node 类 和 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
}

嘿，我知道这个回答有点晚了，但是我有一个快速简单的答案。

代码是用F#编写的，但适用于任何语言。由于这是ML家族中不常见的语言，我将提供一些增强可读性的要点。 F#通过缩进来进行嵌套。函数（嵌套部分）的最后一行代码是返回值。 (x, y) 是一个元组，x::xs 是一个头部为x和尾部为xs（其中xs可以为空）的列表，|> 取最后一行的结果并将其作为参数传递到其右侧的表达式中（增强可读性），最后 (fun args -> some expression) 是一个lambda函数。

// 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.

需要注意的是，这个函数是完全尾递归的，因此不会发生栈溢出的可能性。首先将列表扩展为一个单例列表，在一次操作中完成，可以降低最差情况下的常数因子。由于合并操作是在列表的列表上进行的，我们可以递归地合并和排序内部列表，直到达到固定点，即所有内部列表都被排序成一个列表，然后返回该列表，从而将列表列表合并为一个列表。

这是整段代码的完整部分，展示了如何在Java中创建链表并使用归并排序进行排序。我在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;
        }
    }

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0)
            return null;

        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < lists.length; i++){
            ListNode listNode = lists[i];
            while(listNode != null){
                list.add(listNode.val);
                listNode = listNode.next;
            }
        }
        if(list.size() == 0)
            return null;

        Collections.sort(list);
        ListNode result = new ListNode(list.remove(0));
        list.forEach(v -> doAdd(v, result));
        return result;
    }

    private void doAdd(int val, ListNode node){
        if(node.next == null){
            node.next = new ListNode(val);
            return;
        }
        doAdd(val, node.next);
    }
}

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