Coverage for blog/dsa/leetcode/linked_list_rm/__init__.py: 77%
79 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1from typing import Optional
3import pytest
4from typing_extensions import Self
7# start snippet node
8class ListNode:
9 val: int
10 next: Self | None
12 def __init__(self, val=0, next: Self | None = None):
13 self.val = val
14 self.next = next
16 def __iter__(self):
17 curr = self
18 while curr is not None:
19 yield curr.val
20 curr = curr.next
22 @classmethod
23 def fromItems(cls, *items: int) -> Self:
24 if not items:
25 raise ValueError("At least one item is required.")
27 head = cls(items[0])
29 lastnode = head
30 for k in range(len(items) - 1):
31 item = items[k + 1]
32 node = cls(item)
33 lastnode.next = node
34 lastnode = node
36 return head
37 # end snippet node
40# start snippet solution
41class Solution:
42 def modifiedList(
43 self,
44 nums: list[int],
45 head: ListNode,
46 ) -> Optional[ListNode]:
48 hashed = set(nums)
50 # NOTE: Remove any heads that have bad values.
51 node = head
52 nodelast: ListNode # already checked
53 while node is not None:
54 if node.val not in hashed:
55 break
57 nodelast = node
58 node = node.next # type: ignore[assignment]
60 head_final = node
61 if head_final is None or head_final.next is None:
62 return head_final
64 # NOTE: Delink if value is bad. ``nodelast`` should not be incremented
65 # when a bad value is removed as it is will remain the same.
66 while node is not None:
68 if node.val in hashed:
69 nodelast.next = node.next
70 node = node.next # type: ignore[assignment]
71 else:
72 nodelast = node
73 node = node.next # type: ignore[assignment]
75 return head_final
76 # end snippet solution
79# start snippet solution_2
80class Solution2:
81 def modifiedList(
82 self,
83 nums: list[int],
84 head: ListNode,
85 ) -> Optional[ListNode]:
87 # NOTE: Remove any heads that have bad values.
88 hashed = set(nums)
89 head_final = None
90 is_head = True
91 node = head
92 nodelast: ListNode
94 while node is not None:
95 if is_head:
96 if node.val not in hashed:
97 head_final = node
98 is_head = False
99 continue
101 nodelast = node
102 node = node.next # type: ignore[assignment]
103 nodelast.next = None
104 elif node.val in hashed:
105 nodelast.next = node.next
106 node.next = None
108 node = nodelast.next # type: ignore[assignment]
109 else:
110 nodelast = node
111 node = node.next # type: ignore[assignment]
113 return head_final
114 # end snippet solution_2
117@pytest.fixture
118def solution():
119 return Solution2()
122@pytest.mark.parametrize(
123 "nums, head, answer",
124 (
125 ([1, 2, 3], [1, 2, 3, 4, 5], [4, 5]),
126 ([1], [1, 2, 1, 2, 1, 2], [2, 2, 2]),
127 ([1, 7, 6, 2, 4], [3, 7, 1, 8, 1], [3, 8]),
128 ),
129)
130def test_solution(
131 solution: Solution,
132 nums: list[int],
133 head: ListNode,
134 answer: ListNode,
135):
137 input = ListNode.fromItems(*head)
139 print(list(input))
140 _got = solution.modifiedList(nums, input)
141 assert _got is not None
143 got = list(_got)
144 print(got)
145 assert got == answer