[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ノードと現在のノードノードノードの2つのポインタを使用します.valinノードが表示された場合、prevのnext pointerをnodeのnext pointerとして指定します.現在のノードの値がvalでない場合は、prevをnodeに置き換えます.次にnodeをnodeのnext pointerとして指定し、リストを最後にナビゲートします.
Edge caseに注意してください.headノードからvalが一致します.headがvalに等しい場合、prevはnullであるため、上記のアルゴリズムを適用するとNullPointerExceptionが生成されます.したがって、headノードがvalと一致する場合、headをnodeのnext pointerに設定し、nodeをheadに変更してheadノードを削除します.

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/