






'''simple docstring'''

from typing import Any




class      A     :






 """simple docstring"""





 def __init__(				self      ,  __lowerCAmelCase			):
       UpperCamelCase_					: List[Any]            =				data
       UpperCamelCase_					: int            =				None





 def __repr__(				self			):
       return F"Node({self.data})"






class      A     :






 """simple docstring"""





 def __init__(				self			):
       UpperCamelCase_					: Optional[int]            =				None
 def __iter__(				self			):
       UpperCamelCase_					: Tuple            =				self.head
       while node:
             yield node.data
             UpperCamelCase_					: str            =				node.next
 def __len__(				self			):
       return sum(1 for _ in self			)
 def __repr__(				self			):
       return "->".join([str(lowercase__			) for item in self]			)
 def __getitem__(				self      ,  __lowerCAmelCase			):
       if not 0 <= index < len(self			):
             raise ValueError("""list index out of range."""			)
       for i, node in enumerate(self			):
             if i == index:
                   return node
       return None
 def __setitem__(				self      ,  __lowerCAmelCase      ,  __lowerCAmelCase			):
       if not 0 <= index < len(self			):
             raise ValueError("""list index out of range."""			)
       UpperCamelCase_					: Dict            =				self.head
       for _ in range(lowercase__			):
             UpperCamelCase_					: Dict            =				current.next
       UpperCamelCase_					: List[Any]            =				data
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       self.insert_nth(len(self			)      ,  lowercase__			)
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       self.insert_nth(0      ,  lowercase__			)
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase      ,  __lowerCAmelCase			):
       if not 0 <= index <= len(self			):
             raise IndexError("""list index out of range"""			)
       UpperCamelCase_					: List[Any]            =				Node(lowercase__			)
       if self.head is None:
             UpperCamelCase_					: str            =				new_node
       elif index == 0:
             UpperCamelCase_					: Optional[int]            =				self.head  # link new_node to head
             UpperCamelCase_					: str            =				new_node
       else:
             UpperCamelCase_					: Tuple            =				self.head
             for _ in range(index - 1			):
                   UpperCamelCase_					: List[str]            =				temp.next
             UpperCamelCase_					: Any            =				temp.next
             UpperCamelCase_					: Any            =				new_node
 def 	_UpperCAmelCase							(				self			):  # print every node data
       print(self			)
 def 	_UpperCAmelCase							(				self			):
       return self.delete_nth(0			)
 def 	_UpperCAmelCase							(				self			):  # delete from tail
       return self.delete_nth(len(self			) - 1			)
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase = 0			):
       if not 0 <= index <= len(self			) - 1:  # test if index is valid
             raise IndexError("""List index out of range."""			)
       UpperCamelCase_					: List[str]            =				self.head  # default first node
       if index == 0:
             UpperCamelCase_					: Optional[int]            =				self.head.next
       else:
             UpperCamelCase_					: List[str]            =				self.head
             for _ in range(index - 1			):
                   UpperCamelCase_					: Dict            =				temp.next
             UpperCamelCase_					: Any            =				temp.next
             UpperCamelCase_					: List[str]            =				temp.next.next
       return delete_node.data
 def 	_UpperCAmelCase							(				self			):
       return self.head is None





 def 	_UpperCAmelCase							(				self			):
       UpperCamelCase_					: Tuple            =				None
       UpperCamelCase_					: int            =				self.head

       while current:
             # Store the current node's next node.
             UpperCamelCase_					: int            =				current.next
             # Make the current node's next point backwards
             UpperCamelCase_					: Dict            =				prev
             # Make the previous node be the current node
             UpperCamelCase_					: Tuple            =				current
             # Make the current node the next node (to progress iteration)
             UpperCamelCase_					: Union[str, Any]            =				next_node
       # Return prev in order to put the head at the end
       UpperCamelCase_					: Any            =				prev






def 				snake_case       (  )							->					str:





      """simple docstring"""

      UpperCamelCase_					: List[Any]            =				LinkedList()
      assert linked_list.is_empty() is True
      assert str(a_						) == ""

      try:
            linked_list.delete_head()
            raise AssertionError  # This should not happen.
      except IndexError:
            assert True  # This should happen.

      try:
            linked_list.delete_tail()
            raise AssertionError  # This should not happen.
      except IndexError:
            assert True  # This should happen.

      for i in range(10						):
            assert len(a_						) == i
            linked_list.insert_nth(a_     , i + 1						)
      assert str(a_						) == "->".join(str(a_						) for i in range(1     , 11						)						)

      linked_list.insert_head(0						)
      linked_list.insert_tail(11						)
      assert str(a_						) == "->".join(str(a_						) for i in range(0     , 12						)						)

      assert linked_list.delete_head() == 0
      assert linked_list.delete_nth(9						) == 10
      assert linked_list.delete_tail() == 11
      assert len(a_						) == 9
      assert str(a_						) == "->".join(str(a_						) for i in range(1     , 10						)						)

      assert all(linked_list[i] == i + 1 for i in range(0     , 9						)						) is True

      for i in range(0     , 9						):
            UpperCamelCase_					: List[str]            =				-i
      assert all(linked_list[i] == -i for i in range(0     , 9						)						) is True

      linked_list.reverse()
      assert str(a_						) == "->".join(str(a_						) for i in range(-8     , 1						)						)



def 				snake_case       (  )							->					Optional[Any]:





      """simple docstring"""

      UpperCamelCase_					: Union[str, Any]            =				[
          -9,
          100,
          Node(77_345_112						),
          """dlrow olleH""",
          7,
          5_555,
          0,
          -192.55_555,
          """Hello, world!""",
          77.9,
          Node(10						),
          None,
          None,
          12.20,
      ]
      UpperCamelCase_					: List[Any]            =				LinkedList()

      for i in test_input:
            linked_list.insert_tail(a_						)

      # Check if it's empty or not
      assert linked_list.is_empty() is False
      assert (
          str(a_						) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
          "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
      )

      # Delete the head
      UpperCamelCase_					: str            =				linked_list.delete_head()
      assert result == -9
      assert (
          str(a_						) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None->None->12.2"
      )

      # Delete the tail
      UpperCamelCase_					: List[Any]            =				linked_list.delete_tail()
      assert result == 12.2
      assert (
          str(a_						) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None->None"
      )

      # Delete a node in specific location in linked list
      UpperCamelCase_					: int            =				linked_list.delete_nth(10						)
      assert result is None
      assert (
          str(a_						) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None"
      )

      # Add a Node instance to its head
      linked_list.insert_head(Node("""Hello again, world!"""						)						)
      assert (
          str(a_						)
          == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
          "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
      )

      # Add None to its tail
      linked_list.insert_tail(a_						)
      assert (
          str(a_						)
          == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
          "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
      )

      # Reverse the linked list
      linked_list.reverse()
      assert (
          str(a_						)
          == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
          "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
      )



def 				snake_case       (  )							->					Tuple:





      """simple docstring"""

      from doctest import testmod

      testmod()

      UpperCamelCase_					: List[str]            =				LinkedList()
      linked_list.insert_head(input("""Inserting 1st at head """						).strip()						)
      linked_list.insert_head(input("""Inserting 2nd at head """						).strip()						)
      print("""\nPrint list:"""						)
      linked_list.print_list()
      linked_list.insert_tail(input("""\nInserting 1st at tail """						).strip()						)
      linked_list.insert_tail(input("""Inserting 2nd at tail """						).strip()						)
      print("""\nPrint list:"""						)
      linked_list.print_list()
      print("""\nDelete head"""						)
      linked_list.delete_head()
      print("""Delete tail"""						)
      linked_list.delete_tail()
      print("""\nPrint list:"""						)
      linked_list.print_list()
      print("""\nReverse linked list"""						)
      linked_list.reverse()
      print("""\nPrint list:"""						)
      linked_list.print_list()
      print("""\nString representation of linked list:"""						)
      print(a_						)
      print("""\nReading/changing Node data using indexing:"""						)
      print(f"Element at Position 1: {linked_list[1]}"						)
      UpperCamelCase_					: List[str]            =				input("""Enter New Value: """						).strip()
      print("""New list:"""						)
      print(a_						)
      print(f"length of linked_list is : {len(a_						)}"						)


if __name__ == "__main__":
      main()







from __future__ import annotations

from random import choice






def _lowerCamelCase  (		snake_case  ):
							return choice(snake_case  )






def _lowerCamelCase  (		snake_case     , snake_case  ):
							_lowerCAmelCase							=							random_pivot(snake_case  )

							# partition based on pivot
							# linear time
							_lowerCAmelCase							=							[e for e in lst if e < pivot]
							_lowerCAmelCase							=							[e for e in lst if e > pivot]

							# if we get lucky, pivot might be the element we want.
							# we can easily see this:
							# small (elements smaller than k)
							# + pivot (kth element)
							# + big (elements larger than k)
							if len(snake_case  ) == k - 1:
														return pivot
							# pivot is in elements bigger than k
							elif len(snake_case  ) < k - 1:
														return kth_number(snake_case     , k - len(snake_case  ) - 1  )
							# pivot is in elements smaller than k
							else:
														return kth_number(snake_case     , snake_case  )


if __name__ == "__main__":
				import doctest

				doctest.testmod()






