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:

```
import java.util.LinkedList;
public class Q02 {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(0);
System.out.println("Shuffled list: "+shuffle(list));
}
public static LinkedList shuffle(LinkedList list){
Integer node = 10;
if(list.size()<=1){
return list;
}
LinkedList<Integer>list1 = new LinkedList<>();
LinkedList<Integer>list2 = new LinkedList<>();
while(!list.isEmpty()){
list1.add((Integer) list.removeFirst());
if(!list.isEmpty()){
list2.add((Integer) list.removeFirst());
}
}
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){
list.add(list1.removeFirst());
}
else if(rand == 0){
list.add(list2.removeFirst());
}
}
if(!list1.isEmpty()){
list.add(list2.clone());
}
if(!list2.isEmpty()){
list.add(list1.clone());
}
list.remove(node);
return list;
}
}
```