[leetcode #203] Remove Linked List Elements
2278 ワード
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/
Reference
この問題について([leetcode #203] Remove Linked List Elements), 我々は、より多くの情報をここで見つけました https://velog.io/@timevoyage/leetcode-203-Remove-Linked-List-Elementsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol