# AUG!!! If you have to sort a linked list, sort it in a clean way, JAVA, merge sort with comment.

• /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode previous = new ListNode(0);
previous.next = slower;
// use previous node to keep tracking slower node, because we are going to change the tail of the first half list into null;
while(faster != null && faster.next != null){
previous = previous.next;
slower = slower.next;
faster = faster.next.next;
}
ListNode secondHalf = sortList(slower);
previous.next = null;//this cut the list into half;
return merge(firstHalf, secondHalf);
}
public ListNode merge(ListNode node1, ListNode node2){
if(node1 == null)   return node2;
if(node2 == null)   return node1;
ListNode runningNode1 = node1;
ListNode runningNode2 = node2;
// What we are going to do here is to constructe a full sorted linked list using nodes of those two sorted list one by one.
ListNode helper = new ListNode(0);// this helps us to track the head of final sorted list.
ListNode copy = helper;
while(runningNode1 != null && runningNode2 != null){
// Compare nodes one by one, put them into the correct position until we reach the tail of any list's tail.
if(runningNode1.val > runningNode2.val){
copy.next = runningNode2;
copy = copy.next;
runningNode2 = runningNode2.next;
}else{
copy.next = runningNode1;
copy = copy.next;
runningNode1 = runningNode1.next;
}
}
// Connect the remains with the sorted list and return final result;
if(runningNode1 == null)
copy.next = runningNode2;
else
copy.next = runningNode1;
return helper.next;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.