无序链表排序_双向链表排序算法

    private class Node {
int value;
Node next;
}
private Node getRandomList(int length)
{
Node node = new Node();
int randomNum = (int) ((Math.random() * 100) % 100);
node.value = randomNum;
Node head = node;
for(int i = 0; i < length; i++)
{
randomNum = (int) ((Math.random() * 100) % 100);
Node temp = new Node();
temp.value = randomNum;
node.next = temp;
node = temp;
}
return head;
}
private Node getMiddleNode(Node head)
{
Node index1 = head;
Node index2 = head;
while(index2.next != null && index2.next.next != null)
{
index1 = index1.next;
index2 = index2.next.next;
}
return index1;
}
private Node mergeSort(Node head)
{
if(head.next == null)
return head;
Node middelNode = getMiddleNode(head);
Node head1 = head;
Node head2 = middelNode.next;
middelNode.next = null;
head1 = mergeSort(head1);
head2 = mergeSort(head2);
Node currenthead = mergeSequentialList(head1, head2);
return currenthead;
}
private Node mergeSequentialList(Node head1, Node head2)
{
if(head1 == null)
return head2;
if(head2 == null)
return head1;
Node currentNode = null;
if(head1.value < head2.value)
{
head1.next = mergeSequentialList(head1.next, head2);
currentNode = head1;
}
else
{
head2.next = mergeSequentialList(head1, head2.next);
currentNode = head2;
}
return currentNode;
}
private int outputListValue(Node list, StringBuffer bf) {
// TODO Auto-generated method stub
int i = 0;
while(list.next != null)
{
bf.append(list.value + "-");
i++;
list = list.next;
}
return i;
}
public void main()
{
Node list = getRandomList(50);
list = mergeSort(list);
StringBuffer bf = new StringBuffer();
int count = outputListValue(list, bf);
String result = bf.toString();  
}