Time Complexity Basics

Common time complexities sorted from fastest to slowest:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

LeetCode Training

Chinese site: https://leetcode-cn.com/problemset/all/ English site: https://leetcode.com/

Arrays

Time Complexity

Arrays occupy contiguous memory blocks. Reading an element by index takes O(1) due to direct memory addressing. Inserting or deleting an element at a specific position requires shifting subsequent elements, resulting in O(n) time.

Linked Lists

Summary

• Array: Contiguous memory, O(1) lookup. Insert/delete shift elements, O(n).
• Singly Linked List: Only a next pointer. Doubly linked list has both next and previous. Insertion/deletion at known node is O(1). Lookup requires traversal from head, O(n).

1. Reverse Linked List

Problem links:

• English: https://leetcode.com/problems/reverse-linked-list/
• Chinese: https://leetcode-cn.com/problems/reverse-linked-list/

Reverse a singly linked list. Example: [1,2,3,4,5] becomes [5,4,3,2,1].

Solution

Iterate through the list. For each node, reverse its next pointer to point to the previous node. Since a node has no reference to its predecessor, store the previous node beforehand. Also keep a refeernce to the next node before reassigning the pointer.

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

2. Swap Nodes in Pairs

Problem: Swap every two adjacent nodes in a linked list and return the head.

Example: [1,2,3,4] → [2,1,4,3]

Solution

Use a dummy head to simplify edge cases. Traverse with a temporary pointer temp. If there are at least two nodes after temp, let node1 = temp.next and node2 = temp.next.next. Swap their connections:

temp.next = node2
node1.next = node2.next
node2.next = node1

Then move temp to node1 and continue.

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

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        temp = dummy
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next
            temp.next = node2
            node1.next = node2.next
            node2.next = node1
            temp = node1
        return dummy.next

3. Linked List Cycle Detection

Problem links:

• English: https://leetcode.com/problems/linked-list-cycle/
• Chinese: https://leetcode-cn.com/problems/linked-list-cycle/

Determine if a linked list has a cycle.

Solution

Use Floyd's tortoise and hare alogrithm. Two pointers start at head: one moves one step at a time, the other moves two steps. If they meet, a cycle exists.

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

4. Linked List Cycle II

Problem: Return the node where the cycle begins. If no cycle, return None.

Examples:

• Input: [3,2,0,-4] with tail connecting to index 1 → returns node with value 2
• Input: [1,2] with tail connecting to index 0 → returns node with value 1
• Input: [1] no cycle → returns None

Solution

Let the distance from head to cycle start be a. The fast pointer travels f = a + n*(b+c) + b, where b is the distance from cycle start to meeting point, and c is the remaining cycle length. The slow pointer travels s = a + b. Since f = 2s, we derive that c = a. After the pointers meet, reset one pointer to head and move both at one step per iteration; they meet at the cycle start.

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast is slow:
                break
        else:
            return None  # no cycle
        fast = head
        while fast is not slow:
            fast = fast.next
            slow = slow.next
        return fast