CODEWITHSUNDEEP
javarecursionlinked-list
yiwei
yiwei

Reputation: 4190

Adding an element in a sorted LinkedList

I have a LinkedList of ListElement objects, and I would like to create a recursive method that adds new nodes while still preserving the sorted order of the list.

Right now I have: 

public static ListElement InsertList(ListElement head, ListElement newelem) {

    if (head == null) {
        head = newelem;
        head.next = null;
    } 
    else if (head.next == null) {
        newelem.next = null;
        head.next = newelem;
    }
    else if (head.value < newelem.value) {
        newelem.next = head;
        head = newelem;
    }
    else if (head.value >= newelem.value) {
        head = head.next;
        return InsertList(head, newelem);
    }
    return head;
}

And I am calling it multiple times with the code: 

ListElement head = null;
ListElement elem;

// this block of code is repeated multiple times with values of 3, 8, 20, and 15
elem - new ListElement();
elem.value = 6;
head = InsertList( head, elem );

The output is as follows: 

6
6 3
8 6 3
20 8 6 3
15 8 6 3

This output is correct for the first three lines, but after that it all goes weird. Can anyone please improve my algorithm? I feel like the InsertList method could be shortened a lot more. Thanks!

Upvotes: 1

Views: 2622

Answers (3)

yiwei
yiwei

Reputation: 4190

Thanks for all the help and answers guys!
I found another post similar to mine and one of the answers on there seemed to work for me.
Here is the link for anyone who wishes to see: https://stackoverflow.com/a/15936744/1470257

Upvotes: 0

Vaibhav Desai
Vaibhav Desai

Reputation: 2728

When you try to insert 15, you enter the 4th condition:

// 20 > 15
else if (head.value >= newelem.value)

which in turn calls InsertList but passes 8 as the head node and thus enters the 3rd condition:

// 8 < 15
else if (head.value < newelem.value)

Here, you say 

newelem.next = head;

which sets 15 -> next = 8

and then you say,

head = newelem;

which sets head = 15.

Do you see the problem? Use @Zim-Zam O'Pootertoot answer to fix your bug.

Upvotes: 1

Zim-Zam O&#39;Pootertoot
Zim-Zam O&#39;Pootertoot

Reputation: 18148

The head = head.next statement in your fourth conditional block is destroying the head element. I believe this should instead be

else if(head.value >= newelem.value) {
    head.next = InsertList(head.next, newelem);
}

Upvotes: 1

Related Questions