Leetcode: Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Solution

As we are sorted a linked list, we need that our algorithm works efficiently  when we can only access the data sequentially. Of the three most common sorting algorithms, mergesort, quicksort and heapsort, mergesort is the one that performs better in this situation.
 

/**
 * 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) 
    {
        int count = 0;
        ListNode temp= head;
        if(head == null)
            return null;
        while(temp != null)
        {
            temp = temp.next;
            count++;
        }
        return sort(head, count);
    }
    
    public ListNode sort(ListNode head, int size) 
    {
        if(size==1)
            return head;
        ListNode list2 = head;
        for(int i=0; i<size/2; i++)
            list2 = list2.next;
        ListNode list1 = sort(head, size/2);
        list2 = sort(list2, size-size/2);
        return merge(list1,size/2,list2, size-size/2);
    }
    
    
    
    public ListNode merge(ListNode list1, int sizeList1, ListNode list2, int sizeList2)
    {
        ListNode dummy = new ListNode(0);
        ListNode list = dummy;
        int pointer1 = 0;
        int pointer2 = 0;
        while (pointer1 < sizeList1 && pointer2 < sizeList2)
        {
            if (list1.val < list2.val)
            {
                list.next = list1;
                list1 = list1.next;
                pointer1++;
            }
            else
            {
                list.next = list2;
                list2 = list2.next;
                pointer2++;
            }
            list = list.next;
        }
        for(; pointer1< sizeList1; pointer1++)
        {
            list.next = list1;
            list1 = list1.next;
            list = list.next;
        }
        for(; pointer2< sizeList2; pointer2++)
        {
            list.next = list2;
            list2 = list2.next;
            list = list.next;
        }
        list.next = null;
        return dummy.next;
    }
}