The work. and the fole is below. the code should be done in python
For this programming question, you are to rewrite the merge function but with the input and output type being linked list (defined using the UnorderedList class, included in midterm.py) rather than Python list. Specifically, define a function merge(] that given two (possible empty) sorted linked lists, merges them and returns it as a new sorted linked list. Note: The new list should be made by splicing together the nodes of the first two lists. You may not transform each input linked list into a Python list, merge them and return a linked list from the resulting Python list. You may also NOT concatenate/"merge" the input linked lists, then transform to a Python list, sort the Python list, and transform the sorted Python list back to a linked list. In other words, Python list should not be involved at all Example 1 The first input linked list is 11: 1 -> 1 -> 4 The second input linked list is 12: 1 -> 3 -> 4 When merging them to a single sorted linked list, we get 1-4142434434 1 0 1 0 0 0 Example 2 The first input linked list is 11: 1 -> 3 The second input linked list is 12: 2 -> 5 -> 6 -> 18 Output: 1 - 2 3 4 5 -5 6 -3 10class Node! def _init_(self, data) : self. data = data self . next = None def getData (self) : return self. data def getNext (self) : return self . next def setData (self, data) : self . data = data def setNext (self, node) : self . next = node class UnorderedList! def init_(self) : self . head = None def add (self, data) ! newNode = Node (data] newNode . setNext (self . head) self . head = newNode def length (self) : cur = self. head count = 0 while curt cur = cur . getNext ( ) count +m 1 return count def isEmpty (self) : return self . head am None def search (self, data) : cur = self . head while cur! if cur . getData ( ) mm data: return True cur = cur . getNext [ ) return False def remove (self, data) : if self . head . getData( ) am data: else! self. head = self. head. getNext( ) cur = self. head while cur. getNext ( ) and cur . getNext( ) . getData( ) != data: cur = cur . getNext( ) if cur. getNext ( ) ! cur . setNext (cur . getNext ( ) . getNext( ) ) Given two (possible empty ) sorted linked lists ( defined using the UnorderedList class above), merge them and return it as a new sorted linked list ( defined using the UnorderedList class).Given two (possible empty ) sorted linked lists (defined using the UnorderedList class above), merge them and return it as a new sorted linked list ( defined using the UnorderedList class). The new list should be made by splicing together the nodes of the first two lists. You may not transform each linked list into a Python list, merge them and return a linked list from the resulting Python list. Example 1 Input : 11: 5 -3 10 => 11 -> 12 -> 15 12: 1 3 2 3 5 -> 14 Output : 1 -> 2 -> 5 -> 5 -> 10 -> 11 -> 12 -> 14 -> 15 Example 2 Input : 11: 1 -> 12 :4 2 3 35 3 6 Output : 1 -3 2 -3 3 -3 4 -3 5 -3 6 Example 3 Input ! 11: 1 12: 4 3 5 -36 Output: 1 -> 4 -3 5 -3 6 def merge (li, 12) : # write your code here
