DSA · Lesson 8 of 17

Linked Lists

⏱ 14 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 6 practice problems

Nodes joined by pointers: O(1) insert and delete once you are at a node. Master pointer surgery, dummy heads and the fast/slow technique.

The idea

A singly linked list is a chain of nodes, each holding a value and a next pointer. There is no random access (finding the k-th node is O(k)), but inserting or deleting after a known node is O(1). Interview questions test whether you can rewire pointers without losing part of the list.

Five techniques that solve almost every list problem

Dummy head: a fake node before the head, so deleting or inserting at the front is not a special case.
Reverse in place with prev, curr and next (see the animation).
Fast and slow pointers: fast moves 2, slow moves 1. Use them to find the middle, detect a cycle (Floyd’s algorithm) or find the cycle start.
Gap of n: move one pointer n steps ahead to find the n-th node from the end in one pass.
Merge two sorted lists by always attaching the smaller head; this is the core of merge sort on lists and of Merge k Lists.

Harder problems combine them. Reorder List = find middle + reverse second half + weave. Palindrome List = middle + reverse + compare.

Code template

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

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev

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

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; }
    return prev;
}

ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    return slow;
}

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

ListNode* reverse(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; }
    return prev;
}

ListNode* middle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    return slow;
}

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

function reverse(head) {
  let prev = null, curr = head;
  while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
  return prev;
}

function middle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow;
}

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Complexity

Traversal O(n). Insert or delete after a known node O(1). Search O(n). All five techniques use O(1) extra space.

Practise this pattern (6 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
35	Reverse Linked List	Easy
36	Merge Two Sorted Lists	Easy
37	Middle of the Linked List	Easy
38	Remove Nth Node From End of List	Medium
39	Reorder List	Medium
40	Add Two Numbers	Medium

Common mistakes

Losing the rest of the list: save next before changing curr.next.
Null-pointer errors: check fast and fast.next before fast.next.next.
Returning the old head after reversing: return prev.

Check yourself: how do you detect a cycle in O(1) space?

Floyd’s algorithm. Move slow by 1 and fast by 2; if they ever meet, there is a cycle. If fast reaches null, there is no cycle.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar