So I have writen a program that takes a linkedlist and shuffles it randomly using mergesort algorithm. The problam I'm having now is that the original list loses elements after the shuffle, and after som checking with some outputs it seems that it always one of the extra lists who have elements still left inside them.

This is an assignment and here is the task:

Assume you have as input ia singly-linked list containing N
items (an instance of a LinkedList class in Java). You should rearrange the items in the
LinkedList uniformly at random. Your algorithm should consume a logarithmic (or
constant) amount of extra memory and run in time proportional to NlogN in the worst
case.

my code:

public class Q02 {

public static void main(String[] args) {

System.out.println("Shuffled list: "+shuffle(list));
}

Integer node = 10;
if(list.size()<=1){
return list;
}

while(!list.isEmpty()){
if(!list.isEmpty()){
}
}
shuffle(list1);
shuffle(list2);
if(list2.size() < list1.size()){
int i = (int)(Math.random() * list2.size());
list2.set(i, node);
}

while(!list1.isEmpty()&&!list2.isEmpty()){
int rand = (int)(Math.round(Math.random()));
if(rand == 1){
}
else if(rand == 0){
}
}
if(!list1.isEmpty()){
}
if(!list2.isEmpty()){
}
list.remove(node);
return list;
}

}

I think you have to loop through the list to print out each element instead of just a simple System.out.println(), try using iterator or for loop also works until next element is null (as its the last data in the list)