📘 Singly Linked List – Basics & Problem-Solving Guide

Complete guide to singly linked lists, fundamental operations, patterns, and interview strategies.

Table of Contents

Part 1: Fundamentals

• 1. What Is a Linked List?
• 2. Why Linked Lists?
• 3. Core Terminology

Part 2: Operations & Patterns

• 4. Fundamental Operations
  • 4.1 Traverse
  • 4.2 Insert at Head
  • 4.3 Insert at Tail
  • 4.4 Delete Head
  • 4.5 Delete by Value
• 5. Golden Rules for Linked Lists

Part 3: Problem-Solving

• 6. How to Approach Any Linked List Problem
• 7. Most Important Patterns
• 8. Common Mistakes to Avoid

Part 4: Interview Guide

• 9. Practice Order
• 10. Interview Mindset Tip

1. What Is a Linked List?

A linked list is a linear data structure where each element (node) contains:

• data — the value stored
• a pointer to the next node — the link

Nodes are not stored contiguously in memory.

1.1 Singly Linked List Node

struct ListNode {
    int val;
    ListNode* next;
};

2. Why Linked Lists?

👉 Linked lists shine when frequent insertions/deletions are needed.

3. Core Terminology

• Head → first node
• Tail → last node
• NULL / nullptr → end of list
• Traversal → visiting nodes sequentially

4. Fundamental Operations

4.1 Traverse a Linked List

ListNode* curr = head;
while (curr != nullptr) {
    cout << curr->val << " ";
    curr = curr->next;
}

4.2 Insert at Head

ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* node = new ListNode(val);
    node->next = head;
    return node;
}

4.3 Insert at Tail

ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* node = new ListNode(val);
    if (!head) return node;

    ListNode* curr = head;
    while (curr->next) curr = curr->next;
    curr->next = node;
    return head;
}

4.4 Delete Head

ListNode* deleteHead(ListNode* head) {
    if (!head) return nullptr;
    ListNode* temp = head;
    head = head->next;
    delete temp;
    return head;
}

4.5 Delete by Value

ListNode* deleteByValue(ListNode* head, int val) {
    if (!head) return nullptr;
    if (head->val == val) return deleteHead(head);

    ListNode* curr = head;
    while (curr->next && curr->next->val != val)
        curr = curr->next;

    if (curr->next) {
        ListNode* temp = curr->next;
        curr->next = temp->next;
        delete temp;
    }
    return head;
}

5. Golden Rules for Linked Lists

🔑 Rule 1: Never Lose the Head

Always keep a pointer to the head. If you lose it, the entire list becomes inaccessible.

🔑 Rule 2: Before Accessing

🔑 Rule 3: Dummy Node Pattern

Use dummy nodes to simplify edge cases.

ListNode dummy;
dummy.next = head;
ListNode* curr = &dummy;

Used in:

• Merge lists
• Delete Nth node
• Partition list

6. How to Approach Any Linked List Problem

✅ Step-by-Step Strategy

Step 1: Identify the Pattern

Ask yourself:

• Traversal?
• Two pointers?
• Reversal?
• Merge?
• Cycle detection?

Step 2: Handle Base Cases First

if (!head || !head->next) return head;

Step 3: Draw the List (Mentally or on Paper)

Visualize:

1 → 2 → 3 → 4 → NULL

Track pointer movement step-by-step.

Step 4: Move Pointers Carefully

Update pointers before losing access:

next = curr->next;
curr->next = prev;

Step 5: Return the Correct Node

• Sometimes return head
• Sometimes return dummy.next
• Sometimes return slow or prev

7. Most Important Patterns

🔁 Reversal Pattern

Used in:

• Reverse List
• Reverse K Group
• Palindrome List

🐢🐇 Slow–Fast Pointer (Floyd’s Algorithm)

Used in:

• Find middle
• Detect cycle
• Remove Nth from end

🔗 Merge Pattern

Used in:

• Merge sorted lists
• Sort list (merge sort)

8. Common Mistakes to Avoid

❌ Accessing next without null check
❌ Forgetting to break links
❌ Losing head pointer
❌ Returning wrong node
❌ Mixing object & pointer (ListNode vs ListNode*)

9. Practice Order (Highly Recommended)

Beginner

• Traverse list
• Insert/Delete
• Reverse list

Intermediate

• Middle of list
• Detect cycle
• Merge two lists

Advanced

• Sort list
• Reverse K group
• Copy random pointer list

10. Interview Mindset Tip

When stuck:

“Let me use a dummy node to simplify edge cases.”

This line alone shows strong linked list maturity to interviewers.