Coverage for blog/dsa/leetcode/linked_list_rm/__init__.py: 77%

1from typing import Optional 

2 

3import pytest 

4from typing_extensions import Self 

5 

6 

7# start snippet node 

8class ListNode: 

9 val: int 

10 next: Self | None 

11 

12 def __init__(self, val=0, next: Self | None = None): 

13 self.val = val 

14 self.next = next 

15 

16 def __iter__(self): 

17 curr = self 

18 while curr is not None: 

19 yield curr.val 

20 curr = curr.next 

21 

22 @classmethod 

23 def fromItems(cls, *items: int) -> Self: 

24 if not items: 

25 raise ValueError("At least one item is required.") 

26 

27 head = cls(items[0]) 

28 

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 

35 

36 return head 

37 # end snippet node 

38 

39 

40# start snippet solution 

41class Solution: 

42 def modifiedList( 

43 self, 

44 nums: list[int], 

45 head: ListNode, 

46 ) -> Optional[ListNode]: 

47 

48 hashed = set(nums) 

49 

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 

56 

57 nodelast = node 

58 node = node.next # type: ignore[assignment] 

59 

60 head_final = node 

61 if head_final is None or head_final.next is None: 

62 return head_final 

63 

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: 

67 

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] 

74 

75 return head_final 

76 # end snippet solution 

77 

78 

79# start snippet solution_2 

80class Solution2: 

81 def modifiedList( 

82 self, 

83 nums: list[int], 

84 head: ListNode, 

85 ) -> Optional[ListNode]: 

86 

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 

93 

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 

100 

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 

107 

108 node = nodelast.next # type: ignore[assignment] 

109 else: 

110 nodelast = node 

111 node = node.next # type: ignore[assignment] 

112 

113 return head_final 

114 # end snippet solution_2 

115 

116 

117@pytest.fixture 

118def solution(): 

119 return Solution2() 

120 

121 

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): 

136 

137 input = ListNode.fromItems(*head) 

138 

139 print(list(input)) 

140 _got = solution.modifiedList(nums, input) 

141 assert _got is not None 

142 

143 got = list(_got) 

144 print(got) 

145 assert got == answer