Advanced

Patterns & Tips

A complete reference of linked list and stack patterns, pointer techniques, and common pitfalls. Use this page as a cheat sheet before your interview.

Pattern Cheat Sheet

PatternWhen to UseTemplate
Dummy NodeHead might change (delete/insert at front)dummy = ListNode(0); dummy.next = head
Slow/Fast PointerFind middle, detect cycle, find kth from endslow = fast = head; while fast and fast.next
Three-Pointer ReverseReverse entire list or sublistprev, curr, next_node swap loop
Merge PatternMerge sorted lists, interleavedummy + tail + compare heads
Stack MatchingParentheses, HTML tags, nested structurespush open, pop on close, check match
Monotonic DecreasingNext greater element, stock spanwhile stack and stack[-1] < curr: pop
Monotonic IncreasingNext smaller element, histogram rectwhile stack and stack[-1] > curr: pop
Two StacksUndo/redo, min stack, queue from stacksMain stack + auxiliary stack

Pointer Technique Reference

1. Slow/Fast (Floyd's Algorithm)

# Find middle of linked list
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # middle node

# Detect cycle
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Find kth node from end
def kth_from_end(head, k):
    fast = head
    for _ in range(k):
        fast = fast.next
    slow = head
    while fast:
        slow = slow.next
        fast = fast.next
    return slow  # kth from end

2. Reverse Sublist Template

# Reverse nodes between positions left and right (LC 92)
#
# Before: 1 -> 2 -> 3 -> 4 -> 5, left=2, right=4
# After:  1 -> 4 -> 3 -> 2 -> 5
#
def reverseBetween(head, left, right):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    # Move prev to node before left
    for _ in range(left - 1):
        prev = prev.next

    # Reverse from left to right
    curr = prev.next
    for _ in range(right - left):
        next_node = curr.next
        curr.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node

    return dummy.next

3. Monotonic Stack Template

# Template for "next greater element" type problems
def monotonic_stack_template(arr):
    """
    Decreasing stack: find next greater element
    Increasing stack: find next smaller element
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices

    for i in range(n):
        # For next greater: while stack top is SMALLER
        # For next smaller: while stack top is LARGER
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]  # or i - idx for distance
        stack.append(i)

    return result

Common Pitfalls

⚠
Pitfall 1: Losing the head reference. Always save the head (or use a dummy node) before traversing. Once you move head = head.next, you cannot go back.
⚠
Pitfall 2: Forgetting to handle null/None. Always check if node and if node.next before accessing. Most linked list crashes are NullPointerExceptions.
⚠
Pitfall 3: Order of pointer updates in reversal. Save next_node = curr.next BEFORE changing curr.next. Otherwise you lose the rest of the list.
⚠
Pitfall 4: Using Python // in RPN evaluation. Python's // floors toward negative infinity (-7 // 2 = -4), but LeetCode expects truncation toward zero (-7 / 2 = -3). Use int(a / b) instead.

Decision Tree

# Which pattern to use?
#
#                Is the problem about a linked list?
#               /                                  \
#             YES                                   NO
#              |                                     |
#   Does the head change?               Does it involve LIFO ordering?
#     /              \                      /                  \
#   YES              NO                   YES                  NO
#    |                |                    |                     |
# Dummy Node    Direct traversal    Is it matching/nesting?  Other DS
#    |                |                 /          \
# Reverse?      Find middle?        YES           NO
# Merge?        Detect cycle?        |             |
# Delete?       Kth from end?    Stack Match   Monotonic Stack?
#                                              Next greater?
#                                              Histogram?
#                                              Stock span?

Frequently Asked Questions

Use iterative for production code and when space matters — it is O(1) space. Use recursive when the problem naturally decomposes (like reverse K-group) or when you need to reverse from the tail. In interviews, mention both approaches and let the interviewer choose. If they ask for O(1) space, go iterative.

Look for these signals: "next greater element," "next smaller element," "stock span," "days until warmer," "largest rectangle," or any problem asking about the relationship between an element and the next element that breaks a monotonic property. If a brute-force approach uses nested loops to search forward/backward for a boundary, a monotonic stack can optimize it to O(n).

Sentinel nodes eliminate all edge cases for empty lists and boundary operations. Without sentinels, every insert/remove operation needs if checks for head/tail being None. With sentinels, head.next is always the first real node and tail.prev is always the last. LRU Cache is the perfect example — the sentinel pattern makes the code half the length.

Yes, and it gives true O(1) worst-case push/pop (no amortized resizing). Insert and remove at the head of a singly linked list: push = insert at head, pop = remove head. However, in Python interviews, using a regular list as a stack is standard and expected. Only implement a linked-list-based stack if specifically asked.

Top 10 must-know problems:

  1. Reverse Linked List (LC 206)
  2. Merge Two Sorted Lists (LC 21)
  3. Linked List Cycle (LC 141/142)
  4. LRU Cache (LC 146)
  5. Valid Parentheses (LC 20)
  6. Min Stack (LC 155)
  7. Daily Temperatures (LC 739)
  8. Add Two Numbers (LC 2)
  9. Reorder List (LC 143)
  10. Largest Rectangle in Histogram (LC 84)

If you can solve all 10 confidently, you are well-prepared for any linked list or stack question in an interview.

Three steps:

  1. Draw it out: Always sketch the list and label every pointer before and after each operation. Most bugs are visible on paper.
  2. Print helper: Write a print_list(head) function and call it after each major step during debugging.
  3. Check the order: When reversing or rewiring, ask: "Did I save next before overwriting it? Did I update all required pointers? Did I handle the None case?"

Study Plan

DayFocusProblems to Solve
1LinkedList BasicsReverse List, Middle Node, Merge Two Sorted
2LinkedList IntermediateDetect Cycle, Remove Duplicates, Remove Nth from End
3LinkedList AdvancedReverse K-Group, Add Two Numbers, Reorder List
4Stack BasicsValid Parentheses, Min Stack, Evaluate RPN
5Monotonic StackDaily Temperatures, Next Greater Element, Largest Rectangle
6CombinedLRU Cache, Basic Calculator
7ReviewRe-solve any problem you struggled with. Time yourself.
✅
Final Tip: In your interview, always start by asking clarifying questions: "Is the list singly or doubly linked? Can there be duplicates? What should I return for an empty input?" Then draw a small example, identify the pattern, explain your approach, and only then write code. Communication matters as much as the solution.