Java solution with brief explanation


  • 8
    C

    basic idea is to have two pointers, one for previous node and one for current, if current node.val == val
    we want to set our previous.next to current.next.

    but one problem is what if the head.val == val, I used a while loop to get ride of this situation. So I can be sure that head is always a valid node.

    public ListNode removeElements(ListNode head, int val)
    {

        while(head != null && head.val == val){
            head = head.next;
        }    
        if(head == null)
            return null;
        ListNode pre = head, cur = head.next;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else {
                pre = pre.next;
            }
            cur = cur.next;
        }
        return head;
    }

  • 0
    J

    Thanks, this is a very good solution!


  • 0
    S

    Thanks a lot, your while loop to rid the value before did enlighten me. But still I'm a bit confused: In Java the pointer is realized simply by a '=' assignment?? So you can manipulate the assignee(in your case, prev and cur) to affect the origin value(head)?? I'm using Javascript myself...which seems similar to Java in the aspect of the reference passing of value?


  • 0

    Java is passed by reference, it is obvious that if pre = head then pre.next = nodeA; the head.next will also becomes the nodeA. In javascript object is also pass by reference right? (Plus, JS is more beautiful than Java ^^


  • 0

    This answer use a while loop just for a special case, I dont think it is a good idea. Just like your algorithm cannot process a specific input and you write something like if(input === that specific input) then output the correct answer


  • 0
    S

    thanks for the explanation :)


  • 0
    M

    Good enough to handle the case when head.val == val. There is another alternative: you can put a dummy head in front of the real head, to make sure your following generic solution would always work. Then you can just return dummyHead.next for real head.


  • 0
    F
    public static ListNode removeElements2(ListNode head, int val){
        ListNode dummy = new ListNode(0);
        ListNode fast = dummy;
        ListNode slow = dummy;
        dummy.next = head;
        fast = dummy.next;
        
        while(fast != null){
        	if(fast.val == val){
        		slow.next = fast.next;
        	}else{
        		slow = slow.next;
        	}
        	
        	fast = fast.next;
        }
        
        return dummy.next;
    }
    

    using dummy node


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.