O(n) easy solution in Java

  • 0

    Firstly we'll check for the condition where all the elements in the linked list equals to val. In this case, we'll simply modify the head by iterating through the list.

    Next we'll traverse the whole list and whenever the value equals to Val, we'll go in another loop which will check and remove all the consecutive nodes with value as Val. This will increase the efficiency.

    class Solution {
        public ListNode removeElements(ListNode head, int val) {
           while( head != null && head.val == val) //checking the value in the beginning element
                head = head.next;
            if(head == null) // put null check here(not at the top) because head can be totally null in case if all the value in the list is Val 
                return null;
           ListNode tempNode = head;//saving head for further use
            while(head != null)
                while(null != head.next && head.next.val == val) // iterating till the Val matches the linked list values
                    head.next = head.next.next;
                head = head.next;
            return tempNode;//returning the saved original head

    Since whole list is being traversed and all the process is being done only in one traverse, the time complexity will be O(n).
    Space complexity will be O(1) as we don't need to save any nodes.

Log in to reply

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