In linked list operations, you can either delete nodes directly in the original linked list or use a dummy head node for deletion operations. Let's see which method is more convenient.

203. Remove Linked List Elements

LeetCode Problem Link (opens new window)

Problem: Remove all nodes from the linked list that have a value equal to the given value, val.

Example 1: Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5]

Example 2: Input: head = [], val = 1 Output: []

Example 3: Input: head = [7,7,7,7], val = 7 Output: []

Approach

Let's take an example with the linked list: 1 -> 4 -> 2 -> 4, and remove the element 4.

If you are using C or C++ programming language, do not forget to also remove these two nodes from memory after deleting them from the linked list. After cleaning the memory, it looks like this:

Of course, if you're using Java or Python, you don't need to manage memory manually.

It should be noted that even if you are using C++ for LeetCode and you don't manually delete a node from memory after removal, LeetCode still accepts the solution, although the memory usage may be larger. It is recommended to cultivate the habit of manually clearing memory nonetheless.

When removing an element in this situation, you can have the node's next pointer directly point to the next next node.

Due to the characteristics of a singly linked list, which can only point to the next node, the removal operation differs if it is the head node being removed rather than any other node. How do we handle removing the head node?

This brings us to two methods of linked list operation:

• Operate directly on the original linked list for deletion.
• Set a dummy head node for deletion.

Let's examine the first approach: using the original linked list for removal.

Removing the head node is different from removing other nodes since every other node is removed by its previous node; the head node does not have a previous node.

So, how do we remove the head node? Simply move the head node one position forward, and it is removed from the list.

Don’t forget to delete the original head node from memory.

With the head node removed, you will find that the operations differ for removing the head node versus removing other nodes in a singly linked list. You will notice this when coding since a separate logic is required to handle the removal of the head node.

Can we unify the logic for removing nodes? In fact, we can set a dummy head node to make the process consistent across all nodes.

Let's see how we set a dummy head node using the same linked list to remove element 1.

Here, we're adding a dummy head node as the new head, which will help us remove the original head node element 1.

Now, we can apply the same logic to remove any element, including the head node. Finally, when returning the head node in the problem, remember to return dummyNode->next;, which is the new head node.

Using the original linked list to delete nodes:

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // Remove the head node
        while (head != NULL && head->val == val) { // Note: this is not an 'if' statement
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }

        // Remove non-head nodes
        ListNode* cur = head;
        while (cur != NULL && cur->next != NULL) {
            if (cur->next->val == val) {
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(1)

Using a dummy head node for deletion:

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // Set a dummy head node
        dummyHead->next = head; // Point dummy head node to head for easier deletion
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(1)

You can also solve this problem via recursion:

Base Case: For an empty list, there's no need for removal.

Recursive Case: First, check if the head node's value is val. If it is, remove the head node; the answer is a recursive result on the node's subsequent nodes. If the head node's value isn't val, the answer is the head node concatenated with the new list obtained recursively on the head node’s subsequent nodes.

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // Base Case: Empty list
        if (head == nullptr) {
            return nullptr;
        }

        // Recursive process
        if (head->val == val) {
            ListNode* newHead = removeElements(head->next, val);
            delete head;
            return newHead;
        } else {
            head->next = removeElements(head->next, val);
            return head;
        }
    }
};

• Time Complexity: O(n)
• Space Complexity: O(n)

Other Language Versions

C:

Using the original linked list:

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* temp;
    // When the head node exists and its value equals val
    while(head && head->val == val) {
        temp = head;
        // Set the new head to head->next and free the original head
        head = head->next;
        free(temp);
    }

    struct ListNode *cur = head;
    // When cur and cur->next exist
    while(cur && (temp = cur->next)) {
        // If cur->next value equals val
        if(temp->val == val) {
            // Set cur->next to cur->next->next and free cur->next
            cur->next = temp->next;
            free(temp);
        }
        else
            cur = cur->next;
    }

    // Return the head node
    return head;
}

Using a dummy head node:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeElements(struct ListNode* head, int val){
    typedef struct ListNode ListNode;
    ListNode *dummyHead;
    dummyHead = (ListNode *)malloc(sizeof(ListNode));
    dummyHead->next = head;
    ListNode *cur = dummyHead;
    while(cur->next != NULL){
        if (cur->next->val == val){
            ListNode *tmp = cur->next;
            cur->next = cur->next->next;
            free(tmp);
        }
        else{
            cur = cur->next;
        }
    }
    head = dummyHead->next;
    free(dummyHead);
    return head;
}

Java:

Using the original linked list:

/**
 * Method 1
 * Time Complexity O(n)
 * Space Complexity O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val) {
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null && curr.next !=null) {
        if(curr.next.val == val){
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    return head;
}

/**
 * Method 1
 * Time Complexity O(n)
 * Space Complexity O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // Already null, exit early
    if (head == null) {
        return head;
    }
    // Ensure current head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

Using a dummy head node:

/**
 * Time Complexity O(n)
 * Space Complexity O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    // Set a dummy head node
    ListNode dummy = new ListNode();
    dummy.next = head;

    ListNode cur = dummy;
    while (cur.next != null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;        
        }
    }
    return dummy.next;
}

Recursion

/**
 * Time Complexity O(n)
 * Space Complexity O(n)
 * @param head
 * @param val
 * @return
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }

        // Assume removeElements() returns the complete sublist with removed val nodes
        // At the current recursion level, connect the current node to the sublist
        // Then determine whether current node needs to be removed, if true, return
        // Alternatively, judge removal of current node first; this way, conditional statements are easier to think of
        head.next = removeElements(head.next, val);
        if (head.val == val) {
            return head.next;
        }
        return head;

        // Essentially restore a reconstruction of a list starting backward
    }
}

Python:

(Version 1) Using a Dummy Head Node
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Create a dummy head node to simplify the deletion process
        dummy_head = ListNode(next = head)
        
        # Traverse the list and remove nodes with the value val
        current = dummy_head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        
        return dummy_head.next

Go:

Using the original linked list

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {

	// Define the logic beforehand

	// If the original list's head node equals val, head=head.next, continuously to prevent subsequent head nodes from being Val
	// Here, use a preface loop and check if head is nil to avoid errors
	for head != nil && head.Val == val { // Due to the way LeetCode runs code, the ordering of conditions in the for loop cannot be swapped
		head = head.Next
	}
	cur := head

	for cur != nil && cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}

	return head

}

Using a dummy head node:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head
    cur := dummyHead
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummyHead.Next
}

JavaScript:

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const ret = new ListNode(0, head);
    let cur = ret;
    while(cur.next) {
        if(cur.next.val === val) {
            cur.next =  cur.next.next;
            continue;
        }
        cur = cur.next;
    }
    return ret.next;
};

TypeScript:

Version 1 (Remove directly on the original list):

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function removeElements(head: ListNode | null, val: number): ListNode | null {
    // Remove the head node
    while (head !== null && head.val === val) {
        head = head.next;
    }
    if (head === null) return head;
    let pre: ListNode = head, cur: ListNode | null = head.next;
    // Remove non-head nodes
    while (cur) {
        if (cur.val === val) {
            pre.next = cur.next;
        } else {
            // Without type assertion, the compiler assumes pre is ListNode, pre.next is ListNode | null
            pre = pre.next as ListNode;
        }
        cur = cur.next;
    }
    return head;
};

Version 2 (Dummy head node):

function removeElements(head: ListNode | null, val: number): ListNode | null {
    // Add a dummy node
    const data = new ListNode(0, head);
    let pre = data, cur = data.next;
    while (cur) {
        if (cur.val === val) {
            pre.next = cur.next
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return data.next;
};

Swift:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    let dummyNode = ListNode()
    dummyNode.next = head
    var currentNode = dummyNode
    while let curNext = currentNode.next {
        if curNext.val == val {
            currentNode.next = curNext.next
        } else {
            currentNode = curNext
        }
    }
    return dummyNode.next
}

PHP:

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */

//Version 1 (Remove directly on the original list):
class Solution {

    /**
     * @param ListNode $head
     * @param Integer $val
     * @return ListNode
     */
    function removeElements($head, $val)
    {
  	if ($head == null) {
            return null;
        }

        $now = $head;
        while ($now->next != null) {
            if ($now->next->val == $val) {
                $now->next = $now->next->next;
            } else {
                $now = $now->next;
            }
        }
        if ($head->val == $val) {
            return $head->next;
        }
        return $head;
    }
}

//Version 2 (Dummy head node):
class Solution {

    /**
     * @param ListNode $head
     * @param Integer $val
     * @return ListNode
     */
    function removeElements($head, $val)
    {
        $dummyHead = new ListNode(0, $head);
        $now = $dummyHead;
        while ($now->next != null){
            if ($now->next->val == $val) {
                $now->next = $now->next->next;
            } else {
                $now = $now->next;
            }
        }
        return $dummyHead->next;
    }
}

Rust:

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        let mut dummyHead = Box::new(ListNode::new(0));
        dummyHead.next = head;
        let mut cur = dummyHead.as_mut();
	// Use take() instead of std::mem::replace(&mut node.next, None) for similar effect, and generally more readable
        while let Some(nxt) = cur.next.take() {
            if nxt.val == val {
                cur.next = nxt.next;
            } else {
                cur.next = Some(nxt);
                cur = cur.next.as_mut().unwrap();
            }
        }
        dummyHead.next
    }
}

Scala:

/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
  def removeElements(head: ListNode, `val`: Int): ListNode = {
    if (head == null) return head
    var dummy = new ListNode(-1, head) // Define dummy head node
    var cur = head // cur represents the current node
    var pre = dummy // pre represents the node before cur
    while (cur != null) {
      if (cur.x == `val`) {
        // Equals, then remove; pre points to cur's next
        pre.next = cur.next
      } else {
        // Not equal, pre becomes the current cur node
        pre = cur
      }
      // Iterate further
      cur = cur.next
    }
    // Finally return dummy's next, which is the head of the list
    dummy.next
  }
}

Kotlin:

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        // Use a dummy head, let it point to head
        var dummyNode = ListNode(-1)
        dummyNode.next = head
        // Use cur to traverse nodes
        var cur = dummyNode
        // Check if next node is null
        while (cur.next != null) {
            // If符合condition,移除节点
            if (cur.next.`val` == `val`) {
                cur.next = cur.next.next
            }
            // If不符合condition, traverse next node
            else {
                cur = cur.next
            }
        }
        // 注意: Not returning the dummy node
        return dummyNode.next
    }
}

C#

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution
{
    public ListNode RemoveElements(ListNode head, int val)
    {
        ListNode dummyHead = new ListNode(0,head);
        ListNode temp = dummyHead;
        while(temp.next != null)
        {
            if(temp.next.val == val)
            {
                temp.next = temp.next.next;
            }
            else
            {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}

Ruby#

# Define ListNode
class ListNode
  attr_accessor :val, :next
  def initialize(val = 0, _next = nil)
    @val = val
    @next = _next
  end
end

# Delete nodes with value equal to val
def remove_elements(head, val)
  # Create a dummy head node, making it easier to handle deletions, especially for the head node
  # Dummy node value is set to 0 and points to the current head
  dummy = ListNode.new(0)
  dummy.next = head
  
  # Initialize current as the dummy node
  current = dummy
  
  # Iterate over the list until next of the current node is null
  while current.next
    # If next node's value equals val
    if current.next.val == val
      # Skip the from the list, connecting current's next to the next of the matching node
      current.next = current.next.next
    else
      # Continue traversal if no match
      current = current.next
    end
  end
  
  # Return the head of the new list, pointed by the dummy node's next
  dummy.next
end