Please implement "reverse()" and "sort()" 

class CDLLException(Exception): """ Custom exception class to be used by Circular Doubly Linked List DO NOT CHANGE THIS CLASS IN ANY WAY """ pass class DLNode: """ Doubly Linked List Node class DO NOT CHANGE THIS CLASS IN ANY WAY """ def __init__(self, value: object) -> None: self.next = None self.prev = None self.value = value class CircularList: def __init__(self, start_list=None): """ Initializes a new linked list with sentinel DO NOT CHANGE THIS METHOD IN ANY WAY """ self.sentinel = DLNode(None) self.sentinel.next = self.sentinel self.sentinel.prev = self.sentinel # populate CDLL with initial values (if provided) # before using this feature, implement add_back() method if start_list is not None: for value in start_list: self.add_back(value) def __str__(self) -> str: """ Return content of singly linked list in human-readable form DO NOT CHANGE THIS METHOD IN ANY WAY """ out = 'CDLL [' if self.sentinel.next != self.sentinel: cur = self.sentinel.next.next out = out + str(self.sentinel.next.value) while cur != self.sentinel: out = out + ' <-> ' + str(cur.value) cur = cur.next out = out + ']' return out def length(self) -> int: """ Return the length of the linked list This can also be used as troubleshooting method. This method works by independently measuring length during forward and backward traverse of the list and return the length if results agree or error code of -1 or -2 if thr measurements are different. Return values: >= 0 - length of the list -1 - list likely has an infinite loop (forward or backward) -2 - list has some other kind of problem DO NOT CHANGE THIS METHOD IN ANY WAY """ # length of the list measured traversing forward count_forward = 0 cur = self.sentinel.next while cur != self.sentinel and count_forward < 101_000: count_forward += 1 cur = cur.next # length of the list measured traversing backwards count_backward = 0 cur = self.sentinel.prev while cur != self.sentinel and count_backward < 101_000: count_backward += 1 cur = cur.prev # if any of the result is > 100,000 -> list has a loop if count_forward > 100_000 or count_backward > 100_000: return -1 # if counters have different values -> there is some other problem return count_forward if count_forward == count_backward else -2 def is_empty(self) -> bool: """ Return True is list is empty, False otherwise DO NOT CHANGE THIS METHOD IN ANY WAY """ return self.sentinel.next == self.sentinel # ------------------------------------------------------------------ # def add_front(self, value: object) -> None: """ Adds value to the front of the list. """ node = DLNode(value) temp = self.sentinel.next self.sentinel.next = node node.next = temp temp.prev = node node.prev = self.sentinel return def add_back(self, value: object) -> None: """ Adds value to back of list. """ new_node = DLNode(value) temp = self.sentinel.prev self.sentinel.prev = new_node new_node.prev = temp temp.next = new_node new_node.next = self.sentinel return def insert_at_index(self, index: int, value: object) -> None: """ Adds a new value at the specified index position in the linked list. Index 0 refers to the beginning of the list (right after the front sentinel). """ if index < 0 or index > self.length(): raise CDLLException node = DLNode(value) tempA = self.sentinel for i in range(index): tempA = tempA.next tempB = tempA.next tempA.next = node node.next = tempB tempB.prev = node node.prev = tempA return def remove_front(self) -> None: """ Removes the first node from the list. """ pass def remove_back(self) -> None: """ Removes the last node from the list. """ pass def remove_at_index(self, index: int) -> None: """ Removes a node from the list given its index. """ if index < 0 or index >= self.length(): raise CDLLException curr = self.sentinel for i in range(index): curr = curr.next curr.next = curr.next.next curr.next.prev = curr return def get_front(self) -> object: """ Returns the value from the first node in the list without removing it. """ if self.length() == 0: raise CDLLException return self.sentinel.next def get_back(self) -> object: """ Returns the value from the last node in the list without removing it. """ pass def remove(self, value: object) -> bool: """ Remove the first node in the list that matches the provided value object. The method returns True if some node was actually removed from the list. Otherwise, it returns False. """ pass

  def reverse(self) -> None: """ Reverses the order of the nodes in the list. The reversal must be done in place without creating any copies of existing nodes or an entire existing list. You are not allowed to swap values of the nodes; the solution must change node pointers. Your solution must have O(N) runtime complexity. """ pass def sort(self) -> None: """ Sorts the content of the list in non-descending order. The sorting must be done in place without creating any copies of existing nodes or an entire existing list. You are not allowed to swap values of the nodes; the solution must change node pointers. """ pass 

testing code:

reverse:

test_cases = ( [1, 2, 3, 3, 4, 5], [1, 2, 3, 4, 5], ['A', 'B', 'C', 'D'] )

for case in test_cases:

lst = CircularList(case) lst.reverse() print(lst)

Output: CDLL [5 <-> 4 <-> 3 <-> 3 <-> 2 <-> 1]

CDLL [5 <-> 4 <-> 3 <-> 2 <-> 1]

CDLL [D <-> C <-> B <-> A]

sort:

test_cases = ( [1, 10, 2, 20, 3, 30, 4, 40, 5], ['zebra2', 'apple', 'tomato', 'apple', 'zebra1'], [(1, 1), (20, 1), (1, 20), (2, 20)] ) for case in test_cases: lst = CircularList(case) print(lst) lst.sort() print(lst) Output: CDLL [1 <-> 10 <-> 2 <-> 20 <-> 3 <-> 30 <-> 4 <-> 40 <-> 5] CDLL [1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 10 <-> 20 <-> 30 <-> 40] CDLL [zebra2 <-> apple <-> tomato <-> apple <-> zebra1] CDLL [apple <-> apple <-> tomato <-> zebra1 <-> zebra2] CDLL [(1, 1) <-> (20, 1) <-> (1, 20) <-> (2, 20)] CDLL [(1, 1) <-> (1, 20) <-> (2, 20) <-> (20, 1)]