CODEWITHSUNDEEP
javarecursionlinked-listsingly-linked-list
user3029486
user3029486

Reputation: 289

Destructively delete every other element from a linked list

I'm successfully able to delete every other element from a linked list in a non destructive way (by returning a new linked list). Here's that function: 

public static Link<Integer> everyOther(Link<Integer> link){
    if(link == null) return null; 
    if(link.next == null) return link;
    return new Link(link.data, everyOther(link.next.next)); 
}

For an input list of 1, 2, 3, 4 it successfully returns 1, 3.

However I'm now trying to do this destructively (with void return type) and I'm having trouble. This is my attempt so far: 

public static void everyOtherDestructive(Link<Integer> link){
    if(link == null) return; 
    if(link.next == null) return;
    if(link.next.next != null){
        link.next = link.next.next;
        everyOtherDestructive(link.next); 

    }               
}

This only works for lists of odd lengths but not even. The linked list of 1, 2, 3, 4 should be changed to 1, 3. But instead I'm getting 1, 3, 4.

Can anyone help me understand why it's not skipping over the last element like it should?

Upvotes: 0

Views: 2725

Answers (3)

Nishant
Nishant

Reputation: 1142

This if(link.next.next != null) condition is not required. It skips the last element in even numbered list. Change it as :

public void everyOtherDestructive(Link<Integer> link) {
    if (link == null || link.next == null)
        return;
    else {
        link.next = link.next.next;
        everyOtherDestructive(link.next);

    }
}

Upvotes: 3

Dejan Pekter
Dejan Pekter

Reputation: 735

You have a bug in your code

After you connect first and third, you go to third and try to get fort and fifth, since fifth is null, you can't get it, but it is ok to set next of third to null, so your last if should be deleted and everything will be fine. 

public static void everyOtherDestructive(Link<Integer> link){
    if(link == null) return; 
    if(link.next == null) return;
    link.next = link.next.next;  
    everyOtherDestructive(link.next);           
}

Upvotes: 3

ljgw
ljgw

Reputation: 2771

It's because, when you are at 3, you do nothing (because link.next.next is null).

At that point, you should set link.next to null. This is achieved automatically when you just get rid of the entire if-statement.

public static void everyOtherDestructive(Link<Integer> link){
    if(link == null) return; 
    if(link.next == null) return;
    link.next = link.next.next;
    everyOtherDestructive(link.next); 
}

Upvotes: 3

Related Questions