Remove Linked List Elements
leetcode: https://leetcode.com/problems/remove-linked-list-elements/
Description:
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.
Idea:
**solution 1: move head node **
Step1: if the head node is target node, then delete it by removing head to it’s next unit the new head node isn’t the target
Step2: create temporary index to traverse the list when the current node isn’t null and the next node of current node isn’t null. if one element is the target, then make the current index point to the next next node.
Code:
/**
* 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) {
//if the list is null
if(head == null){
return head;
}
//when the head is target, make the next node as head.
while(head != null && head.val == val){
head = head.next;
}
//set the index to traverse the list
ListNode current = head;
while(current != null){
//when the next node isn't null, and this node is targe，make current node point to next next node
while(current.next != null && current.next.val == val){
current.next =current.next.next;
}
//if the current's next node isn't target, move it to the next
current =current.next;
}
return head;
}
}
Solution 2: Use Dummy Node
Step1: create a new node, and make the next node of it point to the original head node.
Step2: because now the head is new virtual node, so we don’t need to consider the head node again.
Step3; set the current node start from the head node, just search the list, if the element’s val == target, then make the current node point to next next node.
Code:
/**
* 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) {
//if the list is null
if(head == null){
return head;
}
//set the dummy node and make it as new head by making it point to original node
ListNode dummy = new ListNode(-1, head);
//set the index to traverse the list
ListNode current = dummy;
while(current != null){
//when the next node isn't null, and this node is targe，make current node point to next next node
while(current.next != null && current.next.val == val){
current.next =current.next.next;
}
//if the current's next node isn't target, move it to the next
current =current.next;
}
//dummy's next node is real list
return dummy.next;
}
}