---
# System prepended metadata

title: '#4 [Leetcode 203](https://leetcode.com/problems/remove-linked-list-elements/) Remove Linked List Elements'
tags: [leetcode, linked list, easy]

---

# #4 [Leetcode 203](https://leetcode.com/problems/remove-linked-list-elements/) Remove Linked List Elements

###### tags:`linked list` `easy` `leetcode`

<br>

## Issue

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

### Sample Input & Output

![](https://i.imgur.com/77IidzR.jpg)

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

```javascript=
Input: head = [], val = 1
Output: []
```

```javascript=
Input: head = [7,7,7,7], val = 7
Output: []
```

### Constraints

* The number of nodes in the list is in the range [0, 10^4].
* 1 <= Node.val <= 50
* 0 <= val <= 50

<br>

## Solutions

### Most voted

:::spoiler Iteration with dummy
```javascript=
var removeElements = function(head, val) {
  const preHead = new ListNode(0, head);
  let curr = preHead;
  
  while (curr.next !== null) {
    if (curr.next.val === val) {
      curr.next = curr.next.next;
      continue;
    }
    curr = curr.next;
  }
  
  return preHead.next;
};
```
:::

<br>

:::spoiler Iteration without dummy
```javascript=
var removeElements = function(head, val) {
	// The linked list may be empty.
    if (head === null) {
        return head;
    }
    
	// First, handle the head with the matched `val`.
    while (head !== null && head.val === val) {
        head = head.next;
    }
	
	// And then, handle the remaining nodes' values.
    if (head !== null) {
        let curr = head.next;
		// A pointer that actually modifies the linked list.
        let prev = head;
        
        while (curr !== null) {
            if (curr.val === val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            
            curr = curr.next;
        } 
    }
    
    return head;
};
```

* Need to deal with `wrong head` since we need to have a `right start` which maybe a more complicated solution compared to the one with dummy  

:::

<br>

:::spoiler Recrusive
```javascript=
// Time O(n) Space O(n)

function removeElements(head, val){
    if(!head) return null;
    if(head.val === val) return removeElements(head.next, val);
    
    head.next = removeElements(head.next, val);
    return head;
}
```
:::

### Everyone's

:::spoiler 東
```javascript=
// Time: O(n) | Space: O(1) - n is the amount of nodes linked to input head
var removeElements = function(head, val) {
    const dummy = new ListNode();
    dummy.next = head;
    let currNode = dummy;
    while(currNode) {
        let nextNode = currNode.next;
        while(nextNode && nextNode.val === val) {
          nextNode = nextNode.next;  
        }
        currNode.next = nextNode;
        currNode = currNode.next;
    }
    return dummy.next;
};

// recursive:
// Time O(n) | Space O(n), n is the amount of nodes linked to input head
function removeElements(head, val){
    const dummy = new ListNode();
    dummy.next = head;
    function removeTargetNode(currNode){
        if(!currNode) return currNode;
        let nextNode = currNode.next;
        while(nextNode && nextNode.val === val){
            nextNode = nextNode.next;
        }
        currNode.next = nextNode;
        return removeTargetNode(currNode.next);
    }
    removeTargetNode(dummy);
    return dummy.next;
}
```
:::

<br>

:::spoiler Hao
```javascript=
var removeElements = function(head, val) {
  const dummy = new ListNode();
  let newList = dummy;

  let curNode = head;
  while (curNode) {
    if (curNode.val !== val) {
      newList.next = curNode;
      newList = newList.next;
    }
    curNode = curNode.next;
  }
  if (newList.next) newList.next = null;
  
  return dummy.next;
};
```
:::

<br>

:::spoiler Raiy
```javascript=
var removeElements = function(head, val) {
    // time O(n+m) space O(1) n = the nodes of list, m = if the head nodes equals to val
    while(head && head.val === val){
        head = head.next
    }
    
    let currentNode = head
    
    while(currentNode && currentNode.next){
        if(currentNode.next.val === val){
            currentNode.next = currentNode.next.next
        }else{
            currentNode = currentNode.next
        }
    }

    return head  
};

// recursive:
var removeElements = function(head, val) {
    if(!head) return null
    head.next = removeElements(head.next, val)
    
    return head.val === val ? head.next : head
};
```
:::

<br>

:::spoiler YC
```javascript=
/**
 * time: O(n) - where n is the number of nodes in the head
 * space: O(1)
 */

var removeElements = function(head, val) {
    const dummy = new ListNode();
    dummy.next = head;
    let curr = dummy;
    
    while(curr.next){
        if (curr.next.val === val) curr.next = curr.next.next;
        else curr = curr.next;
    }    
    return dummy.next;
};

// recursive:
/**
 * time: O(n) - where n is the number of nodes in the head
 * space: O(n) - where n is the number of nodes in the head
 */

var removeElements = function(head, val) {
    if(!head) return null;
    if(head.val === val){
        return removeElements(head.next, val);
    } 
    head.next = removeElements(head.next, val);
    
    return head;
};
```
:::

<br>

:::spoiler Becky
```javascript=
//time: O(n) | space: O(n)
var removeElements = function(head, val) {
    const dummy = new ListNode();
    dummy.next = head;
    currentNode = dummy;
    while( head ){
        if( head.val === val ){
            currentNode.next = head.next;
        }else{
            currentNode = currentNode.next
        }
        head = head.next;
    }
    return dummy.next;  
};

// recursive:
//time: O(n) | space: O(1)
var removeElements = function(head, val) {
    if (head == null) {
        return null; //終止條件
    }else{
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
};
```
:::

<br>

:::spoiler 月薪
```javascript=
// Time O(n) Space O(1)
var removeElements = function(head, val) {
    let dummy = new ListNode();
    let curNode = dummy;
    while(head){
        if(head.val !== val){
            curNode.next = head;
            curNode = curNode.next;
        }
        head = head.next;
    }
    if(!head && curNode.next && curNode.next.val === val){
        curNode.next = null;
    }
    return dummy.next
};
```
:::

<br>

:::spoiler Sol
:::

<br>

## Discussion

### Remove the last if

Please compare the following two solution: Hao vs YC

### Recursive algorithms
#### Thought Process:
- What's the simplest input?
- pattern

### Implement point
- Base case(when to stop)
- Recursive call