# #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
```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
Sign in with Wallet
Connect another wallet