Linked-List

Challenge Given a linked list, your task is to sort it in ascending order. Solution 1 - TLE Using a bubble sort approach. class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: not_sorted = True if not head: return while not_sorted: tmp = head not_sorted = False while tmp.next: if tmp.val > tmp.next.val: tmp.val, tmp.next.val = tmp.next.val, tmp.val not_sorted = True tmp = tmp.next return head Time Complexity: O(n^2) Solution 2 Using a merge sort approach sort approach. ...

Challenge Given the head of a singly linked list and two integers, reverse the nodes of the list from position left to position right. E.g: reverseBetween(head, 2, 4) 1 -> 2 -> 3 -> 4 -> 5 Returns 1 -> 4 -> 3 -> 2 -> 5 Solution class Solution: def reverse(self, head, steps): tmp = head prev = None tail = head i = 0 while tmp and i < steps: current = tmp n = current.next current.next = prev prev = current tmp = n i+=1 head = current tail.next =n t = head return head def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: tmp=head j = 1 prev = None if right -left ==0: return head while tmp and j < left: prev = tmp tmp=tmp.next j =j+1 a = self.reverse(tmp, right+1 - left) if not prev: return a prev.next = a return head Time complexity: O(n) Space complexity: 1 ...