Basics

Design

707. Design Linked List (Medium)

from typing import Optional


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

    def __str__(self):
        return f"{self.val}{f' -> {self.next}' if self.next else ''}"


class SinglyLinkedList:
    def __init__(self):
        self.sentinel = SinglyLinkedListNode(val=None)
        self.len = 0

    @property
    def head(self):
        return self.sentinel.next

    def goTo(self, index: int) -> Optional[SinglyLinkedListNode]:
        if index == -1:
            return self.sentinel
        elif 0 <= index < self.len:
            p = self.head
            for _ in range(index):
                p = p.next
            return p

    def insert(self, index: int, val):
        if 0 <= index <= self.len:
            prev = self.goTo(index - 1)
            prev.next = SinglyLinkedListNode(val=val, next=prev.next)
            self.len += 1

    def insertAtHead(self, val):
        return self.insert(index=0, val=val)

    def insertAtTail(self, val):
        return self.insert(index=self.len, val=val)

    def get(self, index: int):
        p = self.goTo(index)
        return p.val if p else -1

    def remove(self, index: int):
        if 0 <= index < self.len:
            prev = self.goTo(index - 1)
            prev.next = prev.next.next
            self.len -= 1

    def __len__(self):
        return self.len

    def __str__(self):
        return str(self.sentinel.next)

One pointer

Two pointer

141. Linked List Cycle (Easy)

def hasCycle(self, head: Optional[ListNode]) -> bool:
    """Set"""
    seen = set()
    p = head
    while p:
        if p in seen:
            return True
        seen.add(p)
        p = p.next
    return False

142. Linked List Cycle II (Medium)

def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    """Set"""
    seen = set()
    p = head
    while p:
        if p in seen:
            return p
        seen.add(p)
        p = p.next
    return None