I think LeetCode lack of test cases for Linked List Cycle in this problem


  • -1

    In this problem, I think we need to consider the Linked List Cycle.

    For example, if there have 3 ListNode: A(3), B(4), C(5), A->next = B, B->next = C, C->next = A, and the value which we want remove is 4, the result should be: A->next = C, C->next = A.

    But when I submit a solution does not consider this issue, it also passed all the test cases and have Accepted. I think this is a mistake.

    Consider Linked List Cycle (It has been Accepted):

    class Solution {
    public:
        ListNode *removeElements(ListNode *head, int val) {
    		ListNode *tmp = head;
    		while (tmp && tmp->val == val && tmp->next != head)
                tmp = tmp->next;
    		if (!tmp || (tmp->next == head && tmp->val == val))
                return NULL;
    		head = tmp;
            tmp = head->next;
            int size = 0;
            while (tmp && tmp != head) {
                ++size;
                tmp = tmp->next;
            }
            tmp = head;
            for (; size > 0; --size)
                if (tmp->next->val == val)
                    tmp->next = tmp->next->next;
                else
                    tmp = tmp->next;
            return head;
        }
    };
    

    Does Not Consider Linked List Cycle (It has also been Accepted):

    class Solution {
    public:
        ListNode *removeElements(ListNode *head, int val) {
    		while (head && head->val == val)
    			head = head->next;
    		if (!head)
    			return NULL;
    		ListNode *tmp = head;
    		while (tmp)
    			if (tmp->next && tmp->next->val == val)
    				tmp->next = tmp->next->next;
    			else
    				tmp = tmp->next;
    		return head;
    	}
    };

  • 0
    M

    It was not a mistake. All the test cases are linear lists with no cycles. ('Easy' problem)

    Good observation though. We'll consider the cyclic test case in the future.
    Thanks for your thoughts.


Log in to reply
 

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