Merge Solution - Sort LinkedList

Since the problem requires nlogn solution, merge sort would be a stable one. The tough part of this problem is the divide, which should not miss any nodes/references, that is why the ladder List head goes first than former one. And There are more than one way to actually get the second half reference, I implemented using next.next…

Another tricky part is the merge between two LinkedLists, a preHead which points to the actual one is suggested as to keep the reference of new Head, otherwise it is very easy to move the head to the end.


/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
return mergeSortList(head);
}

private ListNode mergeSortList(ListNode startNode) {

if (startNode == null || startNode.next == null) {
return startNode;
}

ListNode loopOne = startNode;
ListNode loopTwo = startNode.next.next;
while (loopTwo != null && loopTwo.next != null) {
loopOne = loopOne.next;
loopTwo = loopTwo.next.next;
}
ListNode headTwo = mergeSortList(loopOne.next);
loopOne.next = null;
ListNode headOne = mergeSortList(startNode);

return mergeTwoList(headOne, headTwo);
}

private ListNode mergeTwoList(ListNode nodeOne, ListNode nodeTwo) {
   if(nodeOne == null){
       return nodeTwo;
   }
   if(nodeTwo == null){
       return nodeOne;
   }
ListNode headNode = new ListNode(Integer.MIN_VALUE);
ListNode merger = headNode;
// if (nodeOne.val > nodeTwo.val) {
// merger.next = nodeTwo;
// }else{
//    merger.next = nodeOne;
// }
while (nodeOne != null && nodeTwo != null) {
if(nodeOne.val < nodeTwo.val){
   merger.next = nodeOne;
   nodeOne = nodeOne.next;
}else{
   merger.next = nodeTwo;
   nodeTwo = nodeTwo.next;
}
merger = merger.next;
}
if(nodeOne != null){
   merger.next = nodeOne;
}
if(nodeTwo != null){
   merger.next = nodeTwo;
}
return headNode.next;
}
}