Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to iterate through the nodes 1 by 1, while keeping track of 2 pointers, prev and cur. There are 3 cases we need to consider.

    • Case 1: Remove from the start of the list; keep prev as null to signal we're still at the start, and update the head to the next node in our list, cur.next.
    • Case 2: Remove from the body of the list; set prev.next to cur.next such that cur is skipped over and no longer referenced to in our list.
    • Case 3: Move along; the node's value is not equal to val; update prev to cur.

    By the end, our list will no longer reference nodes whose values equal val - their memory will be freed via the JVM garbage collector. We simply return our possibly updated head node.

    Time Complexity
    The time complexity is O(n) where n is the number of nodes within linked list head.

    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            ListNode prev = null;
            ListNode cur = head;
            
            while (cur != null) {
                // Case 1: Removing from start of list
                if (prev == null && cur.val == val) {
                    head = cur.next; // Update head pointer
                } 
                // Case 2: Removing node from middle of list
                else if (prev != null && cur.val == val) {
                    prev.next = cur.next;
                } 
                // Case 3: Node's value is not equal to val
                else {
                    prev = cur;
                }
                cur = cur.next;
            }
            return head;
        }
    }
    

Log in to reply
 

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