Linked-List

Challenge Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. The order of the initial linked list must be preserved. Solution from copy import deepcopy class Solution: def add_to_list(self, head, node,x): node.next = None if head is None and node.val < x: self.left_part = node self.left_tail = node return elif head is None and node.val >= x: self.right_part = node self.right_tail = node return if head == self.left_part: self.left_tail.next = node self.left_tail = node if head == self.right_part: self.right_tail.next = node self.right_tail = node def partition(self, head: ListNode, x: int) -> ListNode: self.left_part = None self.right_part = None tmp = head while tmp: tmp_cpy = deepcopy(tmp) if tmp.val < x: self.add_to_list(self.left_part, tmp_cpy,x) else: self.add_to_list(self.right_part, tmp_cpy,x) tmp = tmp.next tmp = self.left_part if not tmp: return self.right_part self.left_tail.next = self.right_part return self.left_part Time complexity: O(n) Space complexity: O(1) ...

Challenge Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values. Return the linked list after the deletions. e.g 1 -> 2 ->3 ->2 returns 1 -> 3 Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def print_list(self, head): tmp = head while tmp: print(tmp.val, end=", ") tmp = tmp.next def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next tmp = head prev = head while tmp: if oc[tmp.val] > 1 and tmp == head: head = tmp.next prev = head elif oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next self.print_list(head) return head Solution 2 - Using dummy node def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next fake = ListNode() fake.next = head prev = fake tmp = head while tmp: if oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next return fake.next