What's wrong with this answer?


  • 0
    N
    public ListNode removeElements(ListNode head, int val) {
            ListNode dummyHead = new ListNode(0); 
            dummyHead.next = head;
            ListNode p = dummyHead; 
            ListNode node=head;
            while (node!=null) {
                if(node.val==val) {
                    node=node.next;
                } else {
                    p.next=node;
                    p=p.next;
                    node=node.next;
                }
            }
            return dummyHead.next;
        }
    

    At first glance on this problem I think it can be easily solved, then I found my solution is wrong. but when I change it as following it works well. I am confused about why the first answer is wrong?

    public ListNode removeElements(ListNode head, int val) {
            ListNode dummyHead = new ListNode(0); 
            dummyHead.next = head;
            ListNode p = dummyHead; 
            ListNode node=head;
            while (node!=null) {
                if(node.val==val) {
                    p.next=node.next;
                    node=node.next;
                } else {
                    //p.next=node;
                    p=p.next;
                    node=node.next;
                }
            }
            return dummyHead.next;
        }

  • 0
    J

    This is a very common mistake for linked-list.
    here is an example

    1 -> 1 -> 1
    

    And you want to delete all 1s, firstly you have node pointing to 1, then in the while loop

    if(node.val==val)
    

    is hit, so the next line:

    node=node.next;
    

    will be executed. Note that, "node" is just a pointer pointing to the entry of linkedlist. Therefore,
    changing "node"'s pointee does nothing to the linkedlist. Just Like:

    1 -> 1 -> 1
    ^
    |
    node
    

    Then changes to:

    1 -> 1 -> 1
          ^
          |
        node
    

    In your second solution, you change the next pointer of the node, and that will definitely modify the linkedlist


  • 0
    D

    jinyao is right. The first solution fails to solve a specific situation:

    [x,1,y,1,1,1], val = 1
    

    While node moves to the 4th element, which is number 1, during the while loop, you get var node moves down but do nothing with var p. Finally, the list contains [x,y,1,1,1].

    Solution one could be modified to:

    public ListNode RemoveElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0); 
        dummyHead.next = head;
        ListNode p = dummyHead; 
        ListNode node = head;
        while (node != null) {
            if(node.val != val) {
                p.next = node;
                p = p.next;
                node = node.next;
            } else if(node.next == null) {
                p.next = null;
                return dummyHead.next;
            } else{
                node = node.next;
            }
        }
        return dummyHead.next; 
    }
    

Log in to reply
 

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