Linked List

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

def reverseList(head: ListNode) -> ListNode:
    prev = None  # prev points to head of reversed list
    curr = head  # curr points to head of not yet reversed list

    while curr:
        tempNext = curr.next    # Save next node
        curr.next = prev        # Reverse the pointer
        prev = curr             # Move prev forward
        curr = tempNext         # Move curr forward

    return prev  # prev points to new head of reversed list

Strategies:

• Use a dummy head node

• Use a slow (increment once) and fast (increment twice) pointer

• Use two pointers k steps apart to reach k^th node from end of list

• Create a cycle

• Use a doubly linked list if possible

def hasCycle(head: ListNode) -> bool:
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        # In a cycle, fast will always reach slow
        if slow == fast:
            return True

    return False

Time: O(n)

Space: O(1)

def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = curr = ListNode()

    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 or list2
    return dummy.next

Time: O(n)

Space: O(1)

def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = curr = ListNode()
    carry = 0

    while l1 or l2:
        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0
        total = v1 + v2 + carry
        carry = 1 if total > 9 else 0
        curr.next = ListNode(total % 10)

        curr = curr.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    if carry:
        curr.next = ListNode(1)
    return dummy.next

Time: O(n)

Space: O(n) including output

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

def copyRandomList(head: 'Optional[Node]') -> 'Optional[Node]':
    m, curr = {}, head

    # Key: original node; Value: new node
    while curr:
        m[curr] = Node(curr.val)
        curr = curr.next

    # Populate next and random pointers in new nodes
    curr = head
    while curr:
        newNode = m[curr]
        newNode.next = m[curr.next] if curr.next else None
        newNode.random = m[curr.random] if curr.random else None
        curr = curr.next

    return m[head] if head else None

Time: O(n)

Space: O(n)

Alternative solution:

def copyRandomList(head: 'Optional[Node]') -> 'Optional[Node]':
    if not head:
        return None

    # Insert new nodes: old1 -> new1 -> old2 -> new2 ...
    curr = head
    while curr:
        curr.next = Node(curr.val, curr.next)
        curr = curr.next.next

    # Assign random pointers
    curr = head
    while curr:
        curr.next.random = curr.random.next if curr.random else None
        curr = curr.next.next

    # Remove old nodes
    curr = head.next
    while curr.next:
        curr.next = curr.next.next
        curr = curr.next

    return head.next

Time: O(n)

Space: O(n) including output

def reverseBetween(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    if not head.next or left == right:
        return head

    # Get to node before start of sublist
    dummy = before = ListNode(0, head)
    for _ in range(1, left):
        before = before.next

    # start points to first node of sublist i.e. end of reversed sublist
    start = before.next

    # Reverse sublist
    prev = None
    curr = start
    for _ in range(right - left + 1):
        nextTemp = curr.next
        curr.next = prev
        prev = curr
        curr = nextTemp

    before.next = prev # before is node before sublist. prev is start of sublist
    start.next = curr # start is end of sublist. curr is node after sublist

    return dummy.next

Time: O(n)

Space: O(1)

def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    slow = fast = head
    # Loop runs one extra time so that slow points to node before nth node
    for _ in range(n):
        fast = fast.next

    # Reaching end of list means "nth node from end of list" = head
    if not fast:
        return head.next

    while fast.next:
        slow = slow.next
        fast = fast.next

    slow.next = slow.next.next
    return head

Time: O(n)

Space: O(1)

def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    prev, curr = dummy, head

    while curr:
        # Move forward only if duplicate value found
        while curr.next and curr.val == curr.next.val:
            curr = curr.next

        # If curr did not move forward i.e. not duplicate value
        if prev.next == curr:
            prev = curr
            curr = curr.next
        else:
            prev.next = curr.next
            curr = curr.next

    return dummy.next

Time: O(n)

Space: O(1)

def rotateRight(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head:
        return head

    # Get list length and tail pointer
    length, tail = 1, head
    while tail.next:
        length += 1
        tail = tail.next

    k %= length

    # Create cycle
    tail.next = head

    # Traverse to rotated list tail
    for _ in range(length - k):
        tail = tail.next

    newHead = tail.next
    tail.next = None
    return newHead

Time: O(n)

Space: O(1)

def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
    loDummy = loTail = ListNode()
    hiDummy = hiTail = ListNode()

    while head:
        if head.val < x:
            loTail.next = head
            loTail = loTail.next
        else:
            hiTail.next = head
            hiTail = hiTail.next
        head = head.next

    hiTail.next = None
    loTail.next = hiDummy.next
    return loDummy.next

Time: O(n)

Space: O(1)

# Doubly linked list nodes
class ListNode:
    def __init__(self, key=0, val=0, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next

class LRUCache:
    def __init__(self, capacity: int):
        # Key = key; Value = Node pointer
        self.m = {}
        self.capacity = capacity
        # MRU at dummy head, LRU at dummy tail
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.m:
            return -1
        self.removeNode(self.m[key])
        self.moveToHead(self.m[key])
        return self.m[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.m:
            self.removeNode(self.m[key])
            self.moveToHead(self.m[key])
            self.m[key].val = value
        else:
            if len(self.m) >= self.capacity:
                del self.m[self.tail.prev.key]
                self.removeNode(self.tail.prev)
            newNode = ListNode(key, value)
            self.moveToHead(newNode)
            self.m[key] = newNode

    def removeNode(self, node: ListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node: ListNode) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node