编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？

//合并 
//链表结构
struct ListNode
{
    int value;
    ListNode* next;
};

//合并 
ListNode* merge(ListNode *a,ListNode *b) 
{
	ListNode *result=NULL;
	if(a==NULL)	
		return b;
	else if(b==NULL)
		return a;
	
	if(a->value<=b->value)  
    {  
        result=a;  
        result->next=merge(a->next,b);  
    }  
    else  
    {  
        result=b;  
        result->next=merge(a,b->next);     
    }  
    return result; 	
}

//寻找中点 
void findMid(ListNode* source, ListNode** first, ListNode** mid)  
{  
    ListNode* fast;  
    ListNode* slow;  
  
    if(source==NULL||source->next== NULL)  
    {  
        *first=source;  
        *mid=NULL;  
    }  
    else  
    {  
        slow=source;  
        fast=source->next;  
   
        while(fast!=NULL)  
        {  
            fast=fast->next;  
            if(fast!=NULL)  
            {  
                fast=fast->next;  
                slow=slow->next;  
            }  
        }  
  
        *first=source;  
        *mid=slow->next;  
        slow->next=NULL;  
    }  
}  

void listMergeSort(ListNode **p)
{
	ListNode *head=*p;
	ListNode *a,*b;
	
	if(head==NULL||head->next==NULL)
		return ;
	
	findMid(head,&a,&b);
	
	listMergeSort(&a);
	listMergeSort(&b);
	
	*p=merge(a,b);
}

java 代码如下:
//定义链表结构
class ListNode {
	int value;
	ListNode next;
	public ListNode(int _value) {
		this.value = _value;
		this.next = null;
	}
};
public class LinkedMergeSort {
	ListNode listMergeSort(ListNode head) {
		ListNode p = head;
		if (p == null || p.next == null) {
			return p;
		}
		ListNode middle = getMiddle(p);
		ListNode halfNode = middle.next;
		middle.next = null;
		return merge(listMergeSort(head), listMergeSort(halfNode));
	}
	// 寻找中点
	ListNode getMiddle(ListNode head) {
		ListNode fast = null;
		ListNode slow = null;
		if (head == null || head.next == null) {
			return head;
		}
		slow = head;
		fast = head.next.next;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}
	// 合并
	ListNode merge(ListNode head1, ListNode head2) {
		ListNode head = null;
		if (head1 == null)
			return head2;
		if (head2 == null)
			return head1;
		// 按顺序排序插入
		if (head1.value <= head2.value) {
			head = head1;
			head.next = merge(head1.next, head2);
		} else {
			head = head2;
			head.next = merge(head1, head2.next);
		}
		return head;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode head = new ListNode(0);
		head.next = new ListNode(3);
		head.next.next = new ListNode(2);
		head.next.next.next = new ListNode(1);
		LinkedMergeSort linkedMergeSort = new LinkedMergeSort();
		head=linkedMergeSort.listMergeSort(head);
		while (head != null) {
			System.out.print(head.value + "  ");
			head = head.next;
		}
	}
}

public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(0); //增加一个虚拟头结点，方便操作头结点 while (head != null) { ListNode node = dummy; while (node.next != null && node.next.val < head.val) { node = node.next; } ListNode temp = head.next; head.next = node.next; node.next = head; head = temp; } return dummy.next; }