Merge Sort [On linked lists] :(

[Scotty Young]

Im working on an assigment that involves performing a merge sort on a linked list. Im having real trouble understanding not only what code to put down but also how the theory behind it works. What I mean is, I understand mergesort but not how to apply it to linked lists very well.

    
public static LinearNode LinkedMergeSort(LinearNode L)
{
if (L.getNext()!=null)
{
LinearNode temp, tail, lowList, highList;
int mid, index;

mid = countList(L)/2;

temp = L;

for(int i = 0; i < mid; i++)
{
temp.getNext();
}

temp.setNext(highList);
temp = null;
L = lowList;

// form lowList and highList
// making highlist reference second half 
// and unhitching the second half from the first


// Sort the lists with recursive calls
lowList = LinkedMergeSort(lowList);
highList = LinkedMergeSort(highList);


L=null;
tail = null;

// Merge lowList and highList into L
//while there are items on both lists
//compare items at start of the two lists
// make temp ref smaller and remove from its list
// put item temp refs onto end of list L
if(L==null) L=temp;
else tail.setNext(temp);
tail = temp;
tail.setNext(null);
// connect remainder of lowList or highList to end of L

}
return L;
}
 

This is what I have so far. Im working on trying to split the list into 2 halves atm.

Any help would be very much appreciated.