合并排序链表 [英] Merge Sort a Linked List

问题描述

我最近刷牙的一些基础知识，发现合并排序链表是一个pretty的很好的挑战。如果你有一个很好的实现则显示它在这里下车。

I was recently brushing up on some fundamentals and found merge sorting a linked list to be a pretty good challenge. If you have a good implementation then show it off here.

推荐答案

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

Wonder why it should be big challenge as it is stated here, here is a straightforward implementation in Java with out any "clever tricks".

//The main function
public Node merge_sort(Node head) {
    if(head == null || head.next == null) { return head; }
    Node middle = getMiddle(head);      //get the middle of the list
    Node sHalf = middle.next; middle.next = null;   //split the list into two halfs

    return merge(merge_sort(head),merge_sort(sHalf));  //recurse on that
}

//Merge subroutine to merge two sorted lists
public Node merge(Node a, Node b) {
    Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
    while(a !=null && b!= null) {
        if(a.info <= b.info) { curr.next = a; a = a.next; }
        else { curr.next = b; b = b.next; }
        curr = curr.next;
    }
    curr.next = (a == null) ? b : a;
    return dummyHead.next;
}

//Finding the middle element of the list for splitting
public Node getMiddle(Node head) {
    if(head == null) { return head; }
    Node slow, fast; slow = fast = head;
    while(fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    return slow;
}

一些更多的解释在这里 - <一个href="http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list">http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list

这篇关于合并排序链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！