Intermediate

LinkedList Basic Operations

Five essential linked list problems that appear in almost every coding interview. Master these and you will have the foundation for all advanced linked list challenges.

Problem 1: Reverse Linked List (LC 206)

Problem: Given the head of a singly linked list, reverse the list and return the reversed list.

# Before:  1 -> 2 -> 3 -> 4 -> 5 -> None
# After:   5 -> 4 -> 3 -> 2 -> 1 -> None
#
# Step-by-step pointer manipulation:
#
# Step 1:  prev=None  curr=1 -> 2 -> 3 -> 4 -> 5
#          None <- 1    2 -> 3 -> 4 -> 5
#
# Step 2:  None <- 1 <- 2    3 -> 4 -> 5
#
# Step 3:  None <- 1 <- 2 <- 3    4 -> 5
#
# Step 4:  None <- 1 <- 2 <- 3 <- 4    5
#
# Step 5:  None <- 1 <- 2 <- 3 <- 4 <- 5  (done, prev = 5)

def reverseList(head):
    """Reverse a singly linked list iteratively.

    Strategy: Maintain three pointers (prev, curr, next_node).
    At each step, reverse curr's pointer to point to prev.

    Time:  O(n) - visit each node once
    Space: O(1) - only three pointers
    """
    prev = None
    curr = head

    while curr:
        next_node = curr.next   # save next
        curr.next = prev        # reverse pointer
        prev = curr             # advance prev
        curr = next_node        # advance curr

    return prev  # new head


def reverseList_recursive(head):
    """Reverse a singly linked list recursively.

    Base case: empty list or single node.
    Recursive case: reverse the rest, then fix pointers.

    Time:  O(n)
    Space: O(n) - call stack depth
    """
    if not head or not head.next:
        return head

    new_head = reverseList_recursive(head.next)
    head.next.next = head  # point next node back to us
    head.next = None       # remove old forward pointer

    return new_head

Problem 2: Middle of Linked List (LC 876)

Problem: Given the head of a singly linked list, return the middle node. If two middle nodes, return the second one.

# Example: 1 -> 2 -> 3 -> 4 -> 5 -> None
#                     ^
#                   middle (node 3)
#
# Fast/Slow pointer technique:
#
# Step 0:  slow=1, fast=1
# Step 1:  slow=2, fast=3
# Step 2:  slow=3, fast=5
# fast.next is None -> stop. slow = middle!
#
# Even length: 1 -> 2 -> 3 -> 4 -> None
# Step 0:  slow=1, fast=1
# Step 1:  slow=2, fast=3
# Step 2:  slow=3, fast=None (fast is None -> stop)
# Returns second middle (node 3)

def middleNode(head):
    """Find the middle node using slow/fast pointers.

    Slow moves 1 step, fast moves 2 steps.
    When fast reaches the end, slow is at the middle.

    Time:  O(n) - single pass
    Space: O(1) - two pointers
    """
    slow = fast = head

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

    return slow

Problem 3: Linked List Cycle (LC 141)

Problem: Given the head of a linked list, determine if it has a cycle.

# Cycle example:
#
#   1 -> 2 -> 3 -> 4
#             ^    |
#             |    v
#             6 <- 5
#
# Floyd's Cycle Detection (Tortoise and Hare):
#
# Step 0: slow=1, fast=1
# Step 1: slow=2, fast=3
# Step 2: slow=3, fast=5
# Step 3: slow=4, fast=3  (fast looped!)
# Step 4: slow=5, fast=5  -> MEET! Cycle detected.
#
# No cycle:
#   1 -> 2 -> 3 -> None
#   fast reaches None -> no cycle

def hasCycle(head):
    """Detect cycle using Floyd's algorithm.

    If there is a cycle, slow and fast will eventually meet.
    If no cycle, fast will reach None.

    Time:  O(n) - at most 2n steps
    Space: O(1) - two pointers
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False


def detectCycle(head):
    """Find the node where the cycle begins (LC 142).

    After slow and fast meet, reset one pointer to head.
    Move both one step at a time. They meet at cycle start.

    Time:  O(n)
    Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Reset slow to head, move both at speed 1
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow  # cycle start

    return None  # no cycle

Problem 4: Merge Two Sorted Lists (LC 21)

Problem: Merge two sorted linked lists into one sorted list.

# List1: 1 -> 2 -> 4 -> None
# List2: 1 -> 3 -> 4 -> None
#
# Merge process (using dummy node):
#
# dummy -> ?
# Compare 1 vs 1: pick list1's 1
# dummy -> 1 -> ?
# Compare 2 vs 1: pick list2's 1
# dummy -> 1 -> 1 -> ?
# Compare 2 vs 3: pick 2
# dummy -> 1 -> 1 -> 2 -> ?
# Compare 4 vs 3: pick 3
# dummy -> 1 -> 1 -> 2 -> 3 -> ?
# Compare 4 vs 4: pick list1's 4
# dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> ?
# list1 exhausted, append rest of list2
# dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None

def mergeTwoLists(list1, list2):
    """Merge two sorted linked lists.

    Use a dummy node and compare heads of both lists.
    Append the smaller node each time.

    Time:  O(n + m) where n, m are list lengths
    Space: O(1) - reuse existing nodes
    """
    dummy = ListNode(0)
    tail = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    # Attach remaining nodes
    tail.next = list1 if list1 else list2

    return dummy.next

Problem 5: Remove Duplicates from Sorted List (LC 83)

Problem: Given the head of a sorted linked list, delete all duplicates so each element appears only once.

# Before: 1 -> 1 -> 2 -> 3 -> 3 -> None
# After:  1 -> 2 -> 3 -> None
#
# Walk through:
#   curr = 1, curr.next = 1 (duplicate!) -> skip
#   1 -> 2 -> 3 -> 3
#   curr = 1, curr.next = 2 (different) -> advance
#   curr = 2, curr.next = 3 (different) -> advance
#   curr = 3, curr.next = 3 (duplicate!) -> skip
#   1 -> 2 -> 3 -> None
#   curr = 3, curr.next = None -> done

def deleteDuplicates(head):
    """Remove duplicates from a sorted linked list.

    Since the list is sorted, duplicates are adjacent.
    Skip duplicate nodes by adjusting next pointers.

    Time:  O(n) - single pass
    Space: O(1) - in-place
    """
    curr = head

    while curr and curr.next:
        if curr.val == curr.next.val:
            curr.next = curr.next.next  # skip duplicate
        else:
            curr = curr.next            # move forward

    return head

Complexity Summary

Problem	Time	Space	Key Technique
Reverse Linked List	O(n)	O(1)	Three-pointer swap
Middle of List	O(n)	O(1)	Slow/fast pointers
Detect Cycle	O(n)	O(1)	Floyd's algorithm
Merge Two Sorted	O(n+m)	O(1)	Dummy node + compare
Remove Duplicates	O(n)	O(1)	Skip adjacent duplicates