Linkedlist loses elements after shuffling

[Necrozze]

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;
    }

    }

[Slavi]

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)

Take a look at Click Here

[Necrozze]

Well the thing is, when I use System.out.println() on the list before I send it in to shuffle. It displays every element, and now I also got it to work after shuffle by removing the random node I inserted to list2 and then removed from list. If I just delete it from my code and run it, it works perfectly. The print is not the most beautifulest but it works.