Remove Linked List Elements

Problem

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

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

Solution

Concise Recursion: O(n) time, O(n) space

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

Iterative Solution: O(n) time, O(1) space

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) head = head.next;
        ListNode cur = head, prev = new ListNode(0); //cannot set prev == null, NullPointerException 
        while (cur != null) {
            if (cur.val == val) prev.next = null; //This is for corner case like one node linked list 
            else {
                prev.next = cur;
                prev = prev.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

Analysis

This should be a typical problem for Linked List
The recursive solution uses head.next to remove the elements
The iterative solution uses two pointers prev and cur to literally check elements and move

results matching ""

    No results matching ""