CareerCup

Bubble sort? Seriously?

You are right: merge sort is usually a good way to sort a linked list. I wouldn't work for this company.

Given that the lists are Objects in java, there may be concerns about the amount of memory consumed by all the distinct LinkedLists. I suspect, however, that the memory consumed by distinct LinkedLists would be more on the order of O(log n) so it wouldn't be much of an issue.

public static void sort(LinkedList<Integer> list){
    if(list == null){
        throw new NullPointerException();
    }

    //base cases
    if(list.size() == 0 || list.size() == 1){
        return;
    }

    //divide the list and sort each half
    LinkedList<Integer> firstHalf = splitLinkedList(list);
    sort(firstHalf);
    sort(list);

    //recombine the halves
    return merge(list, firstHalf);
}

private static LinkedList<Integer> splitLinkedList(LinkedList<Integer> list){
    LinkedList<Integer> firstHalf = new LinkedList<Integer>();
    int halfSize = list.size() / 2;
    for(int i = 0; i <halfSize ; i++){
        firstHalf.add(list.removeFirst());
    }
    return firstHalf;
}

private static LinkedList<Integer> merge(LinkedList<Integer> list1, LinkedList<Integer> list2){
    LinkedList<Integer> results = new LinkedList<Integer>();
    while(!list1.isEmpty() && !list2.isEmpty()){
        if(list1.peek() < list2.peek()){
            results.add(list1.removeFirst();
        }
        else{
            results.add(list2.removeFirst());
        }
    }
    results.addAll(list1);
    results.addAll(list2);
    return results;
}

May be he is talking about singular Link list in that have only header so in that condition only bubble sort is only way

He was right. In a List you do not have random access (operator[]). You could store a the pointers to each position in a vector but you will need O(n) space. Using bubble sort you use O(1) space, but temporal O(n^2).

So it is a trade-off between size and time efficiency