学步园

就是用List来实现merge sort.

import java.io.*;
import java.util.*;

 class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
     
     static ListNode initializeLinkList(ArrayList<Integer> arrList){
    	 ListNode head = new ListNode(arrList.get(0));
    	 ListNode cNode = head;
    	 for(int i=1;i<arrList.size();i++)
    	 {
    		 cNode.next = new ListNode(arrList.get(i));
    		 cNode = cNode.next;
    	 }
    	 
    	 return head;
     }
     
     static void showList(ListNode head)
     {
    	 while(head != null)
    	 {
    		 System.out.println(head.val);
    		 head = head.next;
    	 }
     }
 }


public class Solution {
	
	public ListNode medianNode(ListNode head)
	{
		ListNode osNode = head;
		ListNode tsNode = head;
		
		while(tsNode.next != null && tsNode.next.next !=null)
		{
			osNode = osNode.next;
			tsNode = tsNode.next.next;
		}
		
		return osNode;
	}
	
	public ListNode mergeList(ListNode head1, ListNode head2)
	{
		if(head1 == null)
			return head2;
		else if(head2 == null)
			return head1;
		
		
		ListNode head = null, cnode = null;
		
		if(head1.val < head2.val)
		{
			head = head1;
			head1 = head1.next;
		}
		else
		{
			head = head2;
			head2 = head2.next;
		}
		
		cnode = head;
		
		while(head1 != null && head2 != null)
		{
			if(head1.val < head2.val)
			{
				cnode.next = head1;
				head1 = head1.next;
			}
			else
			{
				cnode.next = head2;
				head2 = head2.next;
			}
			
			cnode= cnode.next;
		}
		
		while(head1 != null)
		{
			cnode.next = head1;
			cnode = cnode.next;
			head1 = head1.next;
		}
		
		
		while(head2 != null)
		{
			cnode.next = head2;
			cnode = cnode.next;
			head2 = head2.next;
		}
		
		
		return head;
	}
	
	
    public ListNode sortList(ListNode head) {
    	
    	
    	if(head == null || head.next == null)
    		return head;
        
    	ListNode mNode = medianNode(head);
    	
    	ListNode head1 = head;
    	
    	ListNode head2 = mNode.next;
    	
    	mNode.next = null;
    	
    	head1 = sortList(head1);
    	
    	head2 = sortList(head2);
    	
    	head = mergeList(head1,head2);
    	
    	return head;
    }
    

}