203. Remove Linked List Elements

Description

Remove all elements from a linked list of integers that have value val.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 1->2->6->3->4->5->6, val = 6

Output: 1->2->3->4->5

Solutions

ListNode

// 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;
    }
}

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public ListNode removeElements(ListNode head, int val) {
               
        while(head != null && head.val == val) {
            head = head.next;
        }
        
        if(head == null) return null;
        
        ListNode prev = head;
        ListNode curr = head.next;
        
        while(curr != null) {
            if(curr.val != val) {
                prev.next = curr;
                prev = prev.next;
            }
            curr = curr.next;
        }
        
        prev.next = null;
        return head;
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode prev = newHead;
        
        while(prev.next != null) {
            if(prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return newHead.next;
    }
}

Follow up