Jul 29, 2024 | monday 5:00 pm
This series main purpose is for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.
MediumLinked List
Try it yourself here
This problem demonstrates a key fundamental behind linked lists.
Unlike an array, we cannot simply calculate the length of a linked list and directly access the nth element to remove it. However, this disadvantage is balanced by a significant benefit: removing an element from a linked list can be more efficient than removing one from an array.
In an array, elements are stored contiguously in memory. Removing the nth element requires shifting all subsequent elements one position closer, which can be time-consuming for large arrays.
In contrast, a linked list can remove a node from the middle of the list in O(1) time. This is achieved by simply adjusting the ‘next’ pointer of the previous element to point to the nth element’s ‘next’ pointer, effectively bypassing the nth element.
This problem thus illustrates one of the key differences between arrays and linked lists: the trade-off between direct access and efficient insertion/deletion.
Problem Statement: The goal is to remove the nth element from the end of the linked list
Example:
head = [1,2,3,4,5], n = 2
The answer would be [1, 2, 3, 5], as 4 is the 2nd element from the end of the list.
Algorithm:
Complexity:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
pnt1, pnt2 = dummy, head
for _ in range(n):
pnt2 = pnt2.next
while pnt2:
pnt1, pnt2 = pnt1.next, pnt2.next
pnt1.next = pnt1.next.next
return dummy.next
EasyLinked List
Try it yourself here
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
return prev
Complexity:
EasyLinked List
Try it yourself here
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
preHead = ListNode(-1)
curr = preHead
while list1 and list2:
if list1.val < list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
curr.next = list1 if list1 else list2
return preHead.next
Complexity:
MediumLinked List
Try it yourself here
def reorderList(self, head: Optional[ListNode]) -> None:
def middleLL(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseLL(head):
prev = None
curr = head
while curr:
curr.next, prev, curr = prev, curr, curr.next
return prev
middle = middleLL(head)
second = reverseLL(middle)
first = head
while second.next:
first.next, first = second, first.next
second.next, second = first, second.next
Complexity:
MediumLinked List
Try it yourself here
def __init__(self):
self.visitedHash = {}
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
if head in self.visitedHash:
return self.visitedHash[head]
newNode = Node(head.val)
self.visitedHash[head] = newNode
newNode.next = self.copyRandomList(head.next)
newNode.random = self.copyRandomList(head.random)
return newNode
Complexity:
MediumLinked List
Try it yourself here
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
curr = preHead = ListNode(-1)
carry = 0
while l1 or l2 or carry:
l1Val = l1.val if l1 else 0
l2Val = l2.val if l2 else 0
val = l1Val + l2Val + carry
curr.next = ListNode(val % 10)
carry = val // 10
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
curr = curr.next
return preHead.next
Complexity:
EasyLinked List
Try it yourself here
def hasCycle(self, head: ListNode) -> bool:
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
Complexity:
MediumLinked List
Try it yourself here
def findDuplicate(self, nums: List[int]) -> int:
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return fast
Complexity:
MediumLinked List
Try it yourself here
def __init__(self, capacity: int):
self.cap = capacity
self.mp = collections.OrderedDict()
def get(self, key: int) -> int:
if key not in self.mp:
return -1
self.mp.move_to_end(key)
return self.mp[key]
def put(self, key: int, value: int) -> None:
if key in self.mp:
self.mp.move_to_end(key)
self.mp[key] = value
if len(self.mp) > self.cap:
self.mp.popitem(False)
Complexity:
HardLinked List
Try it yourself here
class ListNodeWrapper:
def __init__(self, node: ListNode):
self.node = node
def __lt__(self, other):
return self.node.val < other.node.val
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for l in lists:
if l:
heappush(heap, ListNodeWrapper(l))
preHead = ListNode(-1)
curr = preHead
while heap:
node_wrapper = heappop(heap)
node = node_wrapper.node
curr.next = node
curr = curr.next
if node.next:
heappush(heap, ListNodeWrapper(node.next))
return preHead.next
Complexity:
HardLinked List
Try it yourself here
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
def reverse(node, k):
prev = None
curr = node
while k:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
k -= 1
node.next = curr
return prev
curr = head
size = 0
while curr:
curr = curr.next
size += 1
reversals = size // k
preHead = ListNode(-1, head)
curr = preHead
while reversals:
curr.next = reverse(curr.next, k)
for _ in range(k):
curr = curr.next
reversals -= 1
return preHead.next
Complexity: