CODEWITHSUNDEEP
javaalgorithmdata-structureslinked-listsingly-linked-list
Mona Jalal
Mona Jalal

Reputation: 38225

Removing all the values in the linked list equal to a given value

Can you clarify why not always my code removes all the values in the linked list equal to the given value in the method arguments? How should I fix it? It passes 97% of the testcases. I prefer to fix this rather than changing the whole method using prev/next/dummy pointers.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @param val an integer
     * @return a ListNode
     */
    public ListNode removeElements(ListNode head, int val) {
        while (head!=null && head.val==val){
                head = head.next;
        }
        ListNode tmp=head;

        while (tmp!=null) {
                if (tmp.next!=null && tmp.next.val== val ) {
                    tmp.next=tmp.next.next;
                }
            tmp=tmp.next;
        }
        if (tmp != null) {
            if (tmp.val == val) {
                tmp = tmp.next;
            }
        }
        return head;
    }
}

It doesn't pass this testcase:

Input
5->6->6->null, 6
Output
5->6->null
Expected
5->null

and here's the problem in more details: Given 1->2->3->3->4->5->3, val = 3, you should return the list as 1->2->4->5

Upvotes: 1

Views: 97

Answers (2)

attaboy182
attaboy182

Reputation: 2079

I think this also works:

while (tmp!=null) {
     if (tmp.next!=null && tmp.next.val== val ) {
         tmp.next=tmp.next.next;
      }
      else tmp=tmp.next;
 }

http://code.geeksforgeeks.org/K5yVzm

Upvotes: 0

user2390182
user2390182

Reputation: 73470

Inside your inner while-loop, change:

if (tmp.next!=null && tmp.next.val== val ) {
     tmp.next=tmp.next.next;
}

to

while (tmp.next!=null && tmp.next.val== val ) {
     tmp.next=tmp.next.next;
}

Your version will skip the second of each consecutive pair of values to remove. What you do:

5->6->6->null

-tmp: 5 -> remove first 6, then set tmp to second 6

-tmp: 6, tmp.next: null -> finished (one 6 remains)

Upvotes: 5

Related Questions