[leetcode #203] Remove Linked List Elements

Problem

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, 10⁴].
・ 1 <= Node.val <= 50
・ 0 <= val <= 50

Idea

노드를 탐색하면서 val에 해당하는 값이 나올 경우, 해당 노드를 제거하는 문제다.

리스트의 원리만 이해하면 아주 쉽게 풀 수 있다. prev 노드와 현재 노드인 node 두 pointer를 사용한다.val인 노드가 나왔을 경우 prev의 next pointer를 node의 next pointer로 지정해준다. 현재 노드의 값이 val이 아닐 경우 prev를 node로 바꿔준다. 이후 node를 node의 next pointer로 지정해서 리스트를 끝까지 탐색하면 된다.

Edge case를 주의해야 하는데, 그 경우는 head node부터 val과 일치할 경우다. head가 val과 같으면 prev가 null이기 때문에 위 알고리즘을 적용하면 NullPointerException이 발생한다. 따라서 head node가 val과 일치할 경우 head를 node의 next pointer로 설정하고, node를 head로 바꿔줌으로써 head node를 제거한다.

Solution

/**
 * 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 node = head;
        ListNode prev = null;

        while (node != null) {
            if (node.val == val) {
                if (prev == null) {
                    head = node.next;
                    node = head;
                    continue;
                }
                prev.next = node.next;
                node = node.next;
                continue;
            }
            prev = node;
            node = node.next;
        }

        return head;
    }
}

Reference

https://leetcode.com/problems/remove-linked-list-elements/