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:
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
My Solution
We first create a sentinel node and set it’s next pointer to head. Then we iterate through the list and if the value of the next of the current node is equal to the val, we set the next to the next pointer’s next. If the values don’t match we just move our current node forward. Once we are done iterating through the list, we return the next of the sentinel node to return the head.
Time complexity is O(n) since we iterate through the list once. Space complexity is O(1) since we only require constant extra space.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode sent = new ListNode(-1);
sent.next = head;
ListNode n = sent;
while (n.next != null) {
if (n.next.val == val) {
n.next = n.next.next;
}
else {
n = n.next;
}
}
return sent.next;
}
}