linked lists

Question 1

reverse a linked list
https://neetcode.io/problems/reverse-a-linked-list

Answer 1

prev, curr = None, head

    while curr:
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp

    return prev

Question 2

merge two sorted lists
https://neetcode.io/problems/merge-two-sorted-linked-lists

Answer 2

dummy = node = ListNode()

    while list1 and list2:
        if list1.val < list2.val:
            node.next = list1
            list1 = list1.next
        else:
            node.next = list2
            list2 = list2.next
        node = node.next
    
    node.next = list1 or list2

    return dummy.next

Question 3

design linked list
https://leetcode.com/problems/design-linked-list/submissions/

Answer 3

class ListNode:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None

class MyLinkedList:

def \_\_init\_\_(self):
    self.left = ListNode(0)
    self.right = ListNode(0)
    self.left.next = self.right
    self.right.prev = self.left

def get(self, index: int) -> int:
    curr = self.left.next
    while curr and index > 0:
        curr = curr.next
        index -= 1

    if curr and curr != self.right and index == 0:
        return curr.val

    return -1

def addAtHead(self, val: int) -> None:
    node, next, prev = ListNode(val), self.left.next, self.left
    prev.next = node
    next.prev = node
    node.next = next
    node.prev = prev

def addAtTail(self, val: int) -> None:
    node, next, prev = ListNode(val), self.right, self.right.prev
    prev.next = node
    next.prev = node
    node.next = next
    node.prev = prev

def addAtIndex(self, index: int, val: int) -> None:
    curr = self.left.next
    while curr and index > 0:
        curr = curr.next
        index -= 1
    if curr and index == 0:
        node, next, prev = ListNode(val), curr, curr.prev
        prev.next = node
        next.prev = node
        node.next = next
        node.prev = prev

def deleteAtIndex(self, index: int) -> None:
    curr = self.left.next
    while curr and index > 0:
        curr = curr.next
        index -= 1
    if curr and curr != self.right and index == 0:
        next, prev = curr.next, curr.prev
        next.prev = prev
        prev.next = next

Question 4

design browser history
https://leetcode.com/problems/design-browser-history/description/

Answer 4

View on Github
# Linked List Implementation
class ListNode:
def __init__(self, val, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next

class BrowserHistory:
def __init__(self, homepage: str):
self.cur = ListNode(homepage)

# O(1)
def visit(self, url: str) -> None:
    self.cur.next = ListNode(url, self.cur)
    self.cur = self.cur.next

# O(n)
def back(self, steps: int) -> str:
    while self.cur.prev and steps > 0:
        self.cur = self.cur.prev
        steps -= 1
    return self.cur.val

# O(n)
def forward(self, steps: int) -> str:
    while self.cur.next and steps > 0:
        self.cur = self.cur.next
        steps -= 1
    return self.cur.val

Question 5

number of students unable to eat lunch
https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/description/

Answer 5

res = len(students)
cnt = Counter(students)

for s in sandwiches:
if cnt[s] > 0:
res -= 1
cnt[s] -= 1
else:
return res

resturn res

Question 6

implement stack using queues
https://leetcode.com/problems/implement-stack-using-queues/submissions/

Answer 6

class MyStack:
def __init__(self):
self.q = deque()

def push(self, x: int) -> None:
    self.q.append(x)

def pop(self) -> int:
    for i in range(len(self.q) - 1):
        self.push(self.q.popleft())
    return self.q.popleft()

def top(self) -> int:
    for i in range(len(self.q) - 1):
        self.push(self.q.popleft())
    res = self.q[0]
    self.push(self.q.popleft())
    return res

def empty(self) -> bool:
    return len(self.q) == 0