Linked Lists

Understanding pointers and node-based structures.

Reverse Linked List

What You'll Learn

Pointer manipulation and re-linking nodes.

Real-World Context

"Like reversing a train by changing the couplings between cars so the last car becomes the engine."

Breaking It Down

Initialize three pointers: prev = null, curr = head, next = null
Iterate through the list
Store next node, point current node to prev
Move prev and curr one step forward
Return prev as the new head

Python 3

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

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Line-by-Line Walkthrough

We flip the 'next' pointer of each node to point to the previous node. We need a temporary 'next' pointer to not lose the rest of the list during the flip.

Complexity Analysis

Time: O(N)
Space: O(1)
We visit each node once and use a few pointers.

Common Mistakes

❌ Losing the reference to the next node
✅ Always store curr->next in a temporary variable before changing curr->next.

Try It Yourself

Can you implement this using recursion?

Middle of LL

What You'll Learn

The 'Slow and Fast Pointer' technique (Tortoise and Hare).

Real-World Context

"Finding the middle of a race track by having one person run twice as fast as the other. When the fast person finishes, the slow one is at the middle!"

Breaking It Down

Initialize two pointers: slow and fast at head
Move slow by 1 step and fast by 2 steps
When fast reaches the end, slow is at the middle

Python 3

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Line-by-Line Walkthrough

This is a classic trick to find the middle in a single pass without knowing the length of the list beforehand.

Complexity Analysis

Time: O(N)
Space: O(1)
We traverse the list once.

Common Mistakes

❌ Not checking fast->next in the while condition
✅ This will cause a null pointer exception when fast is at the last node.

Try It Yourself

How would you find the 1/3rd point of a linked list?

Detect Cycle

What You'll Learn

Floyd's Cycle-Finding Algorithm.

Real-World Context

"Checking if a track is a loop or a straight line. If two people run at different speeds on a loop, they will eventually meet!"

Breaking It Down

Use slow and fast pointers
If they ever meet, there is a cycle
If fast reaches null, there is no cycle

Python 3

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

Line-by-Line Walkthrough

If there's a loop, the fast pointer will eventually 'lap' the slow pointer. If there's no loop, the fast pointer will hit the end of the list.

Complexity Analysis

Time: O(N)
Space: O(1)
In the worst case, we traverse the loop once.

Common Mistakes

❌ Starting slow and fast at different positions
✅ They should both start at the head for the logic to be consistent.

Try It Yourself

If a cycle is detected, how do you find the starting node of the cycle?

Merge Sorted LL

What You'll Learn

Merging two sorted structures using pointers.

Real-World Context

"Combining two sorted lists into one single sorted list. Like merging two lines of people sorted by height."

Breaking It Down

Create a dummy node to start the new list
Compare heads of both lists
Attach the smaller node to the new list
Move the pointer of the list that provided the node
Attach any remaining nodes at the end

Python 3

def merge_lists(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

Line-by-Line Walkthrough

We use a dummy node to simplify the logic of starting the new list. We then just pick the smaller element at each step.

Complexity Analysis

Time: O(N + M)
Space: O(1)
We only use a few pointers and don't create new nodes.

Common Mistakes

❌ Forgetting to attach the remaining nodes
✅ When one list ends, the other might still have nodes. Always attach the remainder.

Try It Yourself

Can you merge two sorted linked lists using recursion?

Nth Node from End

What You'll Learn

The 'Gap' technique with two pointers.

Real-World Context

"Finding a node relative to the end without knowing the total length."

Breaking It Down

Move a 'fast' pointer N steps ahead
Start a 'slow' pointer at the head
Move both until 'fast' reaches the end
The 'slow' pointer is now at the Nth node from the end

Python 3

def nth_from_end(head, n):
    fast = slow = head
    for _ in range(n):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    return slow

Line-by-Line Walkthrough

By creating a gap of N between the two pointers, when the first one hits the end, the second one is exactly N steps behind it.

Complexity Analysis

Time: O(N)
Space: O(1)
We traverse the list once.

Common Mistakes

❌ Not handling cases where N is larger than the list length
✅ Add a check to see if 'fast' becomes null during the initial N steps.

Try It Yourself

How would you delete the Nth node from the end instead of just finding it?

Matrix Operations

Working with 2D arrays and nested loops.

Transpose Matrix

What You'll Learn

Swapping elements across the diagonal.

Real-World Context

"Flipping a grid over its diagonal. Rows become columns and columns become rows."

Breaking It Down

Iterate through the upper triangle of the matrix (i < j)
Swap matrix[i][j] with matrix[j][i]

Python 3

def transpose(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    return matrix

Line-by-Line Walkthrough

We only iterate through the upper triangle (j > i) to avoid swapping elements back to their original positions.

Complexity Analysis

Time: O(N²)
Space: O(1)
We visit half of the elements in a 2D grid.

Common Mistakes

❌ Iterating through the whole matrix
✅ If you swap everything, you'll swap them twice and end up with the original matrix!

Try It Yourself

Can you transpose a non-square matrix (M x N)?

Spiral Matrix

What You'll Learn

Boundary management in 2D arrays.

Real-World Context

"Printing a matrix in a spiral order (right, down, left, up)."

Breaking It Down

Define boundaries: top, bottom, left, right
While boundaries don't cross:
1. Print top row, increment top
2. Print right column, decrement right
3. Print bottom row, decrement bottom
4. Print left column, increment left

Python 3

def spiral_order(matrix):
    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for i in range(left, right + 1): res.append(matrix[top][i])
        top += 1
        for i in range(top, bottom + 1): res.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for i in range(right, left - 1, -1): res.append(matrix[bottom][i])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1): res.append(matrix[i][left])
            left += 1
    return res

Line-by-Line Walkthrough

The key is to carefully update the boundaries after each row or column is processed to avoid re-printing elements.

Complexity Analysis

Time: O(N*M)
Space: O(1) (excluding result array)
We visit each element exactly once.

Common Mistakes

❌ Forgetting the inner checks (top <= bottom)
✅ After incrementing top or decrementing right, the boundaries might have crossed. Always check before the next loop.

Try It Yourself

Can you generate a square matrix of size N filled with elements from 1 to N² in spiral order?

Matrix Addition

What You'll Learn

Element-wise operations in 2D arrays.

Real-World Context

"Adding two matrices of the same dimensions."

Breaking It Down

Check if dimensions are equal
Iterate through rows and columns
Add corresponding elements: C[i][j] = A[i][j] + B[i][j]

Python 3

def add_matrices(A, B):
    rows, cols = len(A), len(A[0])
    res = [[0]*cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            res[i][j] = A[i][j] + B[i][j]
    return res

Line-by-Line Walkthrough

Matrix addition is only possible if both matrices have the same number of rows and columns.

Complexity Analysis

Time: O(N*M)
Space: O(N*M)
We visit each element once and store the result.

Common Mistakes

❌ Trying to add matrices of different sizes
✅ Always validate dimensions before performing the operation.

Try It Yourself

Can you implement Matrix Subtraction?

Delete Node

What You'll Learn

Modifying linked list structure.

Real-World Context

"Removing a node from a linked list given its value."

Breaking It Down

Handle head deletion separately
Iterate to find the node before the one to be deleted
Update its 'next' pointer to skip the target node

Python 3

def delete_node(head, val):
    if not head: return None
    if head.val == val: return head.next
    curr = head
    while curr.next and curr.next.val != val:
        curr = curr.next
    if curr.next:
        curr.next = curr.next.next
    return head

Line-by-Line Walkthrough

To delete a node, you need to change the 'next' pointer of the *previous* node to point to the *next* node of the one you're deleting.

Complexity Analysis

Time: O(N)
Space: O(1)
In the worst case, we traverse the whole list.

Common Mistakes

❌ Not handling the head node deletion
✅ The head is a special case because there's no 'previous' node to it.

Try It Yourself

How would you delete a node if you only have a pointer to that node (and not the head)?

Advanced Mastery

Linked lists and Matrices are the gateway to advanced DSA. The remaining questions like "Merge Sorted LL" and "Spiral Matrix" are common interview favorites.

Next: Patterns & Strategy →