Linked List (Cracking the Coding Interview, C++ Version)

This article collects C++-based, Linked List section of Cracking the Coding Interview, including common interview problems, clean implementations, and frequently asked clarifications.

---

What Is a Linked List

A linked list is a sequence of nodes where each node contains:

• A value (data)

• A pointer to the next node

Unlike arrays, linked lists are dynamic and support efficient insertions and deletions without shifting elements. However, they do not support constant-time access to arbitrary elements.

---

Singly Linked List Structure

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

---

Adding a Node at the End

void append(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (!head) {
        head = newNode;
        return;
    }
    Node* curr = head;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = newNode;
}

Why this works: We traverse to the last node (curr->next == nullptr) and set its next to the new node.

---

Deleting a Node by Value

void deleteByValue(Node*& head, int value) {
    if (!head) return;
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* curr = head;
    while (curr->next && curr->next->data != value) {
        curr = curr->next;
    }
    if (curr->next) {
        Node* temp = curr->next;
        curr->next = temp->next;
        delete temp;
    }
}

Why we check head first: Because the node to delete might be the first.

---

Buffer: What It Means

In coding interview terms, a buffer refers to extra memory, usually in the form of:

• A set

• A map

• An array

For example: unordered_set<int> seen; is a buffer to track duplicates.

If an interviewer says “without using extra space or buffer,” you must solve it in-place (e.g., nested loops).

---

Common Interview Problems (C++ Solutions)

2.1 Remove Duplicates from an Unsorted Linked List

Hint:

• #9: Have you tried a hash table?

• #40: Try using a hash set to track duplicates. If you can’t use extra space, think about comparing every node to every other node.

void removeDuplicates(Node* head) {
    unordered_set<int> seen;
    Node* curr = head;
    Node* prev = nullptr;

    while (curr) {
        if (seen.count(curr->data)) {
            prev->next = curr->next;
            delete curr;
        } else {
            seen.insert(curr->data);
            prev = curr;
        }
        curr = prev->next;
    }
}

---

2.2 Return Kth to Last

Hint:

• #8: Start with a brute force solution.

• #25: Can you do it iteratively? What would two pointers help you with?

• #41: Try thinking recursively. What would the return value be?

• #67: If you had the length of the list, could you find the kth to last element?

• #126: You might need a counter that’s passed by reference.

Node* kthToLast(Node* head, int k) {
    Node* fast = head;
    Node* slow = head;

    for (int i = 0; i < k; ++i) {
        if (!fast) return nullptr;
        fast = fast->next;
    }

    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

---

2.3 Delete Middle Node (Given Only That Node)

bool deleteNode(Node* node) {
    if (!node || !node->next) return false;
    Node* temp = node->next;
    node->data = temp->data;
    node->next = temp->next;
    delete temp;
    return true;
}

---

2.4 Partition List Around a Value x

Hint:

• #3: Remember that the partition element doesn’t need to appear in the exact middle—it just needs to be after all smaller elements.

• #24: Consider building two separate lists and merging them at the end.

Node* partition(Node* node, int x) {
    Node* beforeStart = nullptr;
    Node* beforeEnd = nullptr;
    Node* afterStart = nullptr;
    Node* afterEnd = nullptr;

    while (node) {
        Node* next = node->next;
        node->next = nullptr;

        if (node->data < x) {
            if (!beforeStart) beforeStart = beforeEnd = node;
            else {
                beforeEnd->next = node;
                beforeEnd = node;
            }
        } else {
            if (!afterStart) afterStart = afterEnd = node;
            else {
                afterEnd->next = node;
                afterEnd = node;
            }
        }

        node = next;
    }

    if (!beforeStart) return afterStart;
    beforeEnd->next = afterStart;
    return beforeStart;
}

---

Helper Function: Print a Linked List

void printList(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL\n";
}

---

Tips

• Always handle nullptr edge cases.

• Use fast/slow pointer technique for many list problems.

• Be careful with pointer updates during deletions.