203.md

203. Remove Linked List Elements

Description

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

Thinking Process

1. Create a dummy node that points to the original head of the list
2. Save the last node whose value is not val as prev
3. Whenever a target node t is observed, point prev to t.next, update t accordingly
4. Return dummy.next as the result of the new linked list

Code

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

Complexity

1. Time complexity is O(n) as the list is scanned once
2. Space complexity is O(1) since no addtional data structures are used

Observation

1. It is usually useful to create a dummy head for linked list problems