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.
Example 1:
1 -> 2 -> (6) -> 3 -> 4 -> 5 -> (6)
|
v
1 -> 2 -> 3 -> 4 -> 5
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: []
Constraints:
- The number of nodes in the list is in the range [0, 104].
- 1 <=
Node.val <= 50
- 0 <= val <= 50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
''' Recursive '''
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if not head:
return head
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else head
''' Iterative '''
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
sentinel = ListNode(0)
sentinel.next = head
prev, curr = sentinel, head
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return sentinel.next
|