Java O(n) Easy To Understand, Optimal Solution

  • 0

    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,
    • Case 2: Remove from the body of the list; set to 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 =; // Update head pointer
                // Case 2: Removing node from middle of list
                else if (prev != null && cur.val == val) {
                // Case 3: Node's value is not equal to val
                else {
                    prev = cur;
                cur =;
            return head;

Log in to reply

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