Merging two sorted LinkedList using TreeSet

I am trying to merge two sorted LinkedList by using TreeSet, since they already sort it themselves (Although an exception that, both the linkedList dont have common elements). The problem here is, a mysterious ‘0’ is appended at the LinkedList I am trying to return which I am unable to ascertain.

Node gimmeNode(Node root, TreeSet<Integer> st){
Node temp = root;
Node toPrint = root;
Iterator it = st.iterator();
while(it.hasNext()){
    temp.data = (int) it.next();
    temp.next = new Node();
    temp = temp.next;
}
return root;
}

Node MergeLists(Node headA, Node headB) {
Node root = new Node();
TreeSet<Integer> st = new TreeSet<>();
if(headA==null)
    return headB;
else if(headB==null)
    return headA;
else{

    while(headA != null){
        st.add(headA.data);
        System.out.println("AddedA : " + headA.data);
        headA = headA.next;

    }


    while(headB != null){
        st.add(headB.data);
        System.out.println("AddedB : " + headB.data);
        headB = headB.next;
    }
    root = gimmeNode(root, st);
    return root;
}



}

Output

AddedA : 1
AddedA : 3
AddedA : 5
AddedA : 6
AddedB : 2
AddedB : 4
AddedB : 7
LinkedList : 1 2 3 4 5 6 7 0

Answer

gimmeNode has a new Node() at its end. This should not be the case – it should point to null. Therefore, the new Node(), since it’s default constructed, has a 0. This is your extraneous 0. You should implement a mechanism to check if you’re at the last element of the TreeSet – a trivial counter would do. If you’re at the last element, don’t set temp.next = new Node();, leave it null.

Leave a Reply

Your email address will not be published. Required fields are marked *