Linked List Fundamentals

Unlike arrays, which occupy contiguous memory blocks, linked lists connect data scattered across different memory locations using pointers. This structure makes inserting and deleting nodes highly efficient.

A typical singly linked list node can be defined as follows:

struct SinglyNode {
    int data;
    SinglyNode* successor;
    SinglyNode(int x) : data(x), successor(nullptr) {}
};

If a custom constructor is omitted, the compiler provides a default one, requiring manual field assignment:

SinglyNode* start = new SinglyNode();
start->data = 10;

The successor pointer of the final node in the list always points to nullptr, indicating the end of the sequence.

Deleting Target Nodes

When removing a node, the predecessor's pointer must bypass the deleted node and link directly to the successor. It is crucial to release the heap memory of the removed node to prevent leaks. A temporary pointer should store the address of the node to be deleted before altering links, ensuring safe deallocation afterward.

Handling the head node separately often complicates logic. Introducing a sentinel (dummy head) node standardizes deletion operations for all nodes:

class Solution {
public:
    SinglyNode* removeElements(SinglyNode* start, int target) {
        SinglyNode* sentinel = new SinglyNode(0);
        sentinel->successor = start;
        SinglyNode* traverse = sentinel;
        
        while (traverse->successor != nullptr) {
            if (traverse->successor->data == target) {
                SinglyNode* toDelete = traverse->successor;
                traverse->successor = traverse->successor->successor;
                delete toDelete;
            } else {
                traverse = traverse->successor;
            }
        }
        SinglyNode* newStart = sentinel->successor;
        delete sentinel;
        return newStart;
    }
};

Implementing a Custom Linked List

Designing a complete linked list involves managing a sentinel node and tracking the list size. The following class implements core functionalities: retrieval by index, insertion at the head or tail, insertion by index, and deletion by index.

class CustomList {
private:
    struct Node {
        int value;
        Node* next;
        Node(int v) : value(v), next(nullptr) {}
    };
    
    Node* m_sentinel;
    int m_length;

public:
    CustomList() {
        m_sentinel = new Node(0);
        m_length = 0;
    }

    int get(int idx) {
        if (idx < 0 || idx >= m_length) return -1;
        Node* current = m_sentinel->next;
        while (idx--) current = current->next;
        return current->value;
    }

    void addAtHead(int val) {
        Node* fresh = new Node(val);
        fresh->next = m_sentinel->next;
        m_sentinel->next = fresh;
        m_length++;
    }

    void addAtTail(int val) {
        Node* fresh = new Node(val);
        Node* current = m_sentinel;
        while (current->next != nullptr) current = current->next;
        current->next = fresh;
        m_length++;
    }

    void addAtIndex(int idx, int val) {
        if (idx > m_length) return;
        if (idx < 0) idx = 0;
        Node* fresh = new Node(val);
        Node* current = m_sentinel;
        while (idx--) current = current->next;
        fresh->next = current->next;
        current->next = fresh;
        m_length++;
    }

    void deleteAtIndex(int idx) {
        if (idx < 0 || idx >= m_length) return;
        Node* current = m_sentinel;
        while (idx--) current = current->next;
        Node* toRemove = current->next;
        current->next = current->next->next;
        delete toRemove;
        toRemove = nullptr; // Prevent dangling pointers
        m_length--;
    }
};

Reversing a Linked List

Two-Pointer Technique

Iterative reversal utilizes a preceding pointer and a current pointer to invert links sequentially.

class Solution {
public:
    SinglyNode* reverseList(SinglyNode* start) {
        SinglyNode* preceding = nullptr;
        SinglyNode* current = start;
        while (current != nullptr) {
            SinglyNode* upcoming = current->successor;
            current->successor = preceding;
            preceding = current;
            current = upcoming;
        }
        return preceding;
    }
};

Forward Recursion

The recursive approach mirrors the two-pointer method by passing state through function arguments:

class Solution {
private:
    SinglyNode* invert(SinglyNode* preceding, SinglyNode* current) {
        if (current == nullptr) return preceding;
        SinglyNode* upcoming = current->successor;
        current->successor = preceding;
        return invert(current, upcoming);
    }
public:
    SinglyNode* reverseList(SinglyNode* start) {
        return invert(nullptr, start);
    }
};

Every execution path in a recursive function must return a value. Omitting the return keyword during the recursive call will cause compilation errors.

Backward Recursion

This strategy processes the list from tail to head. The base case identifies the new head. During the unwind phase, each node reverses the link with its successor:

class Solution {
public:
    SinglyNode* reverseList(SinglyNode* start) {
        if (start == nullptr || start->successor == nullptr) return start;
        SinglyNode* newHead = reverseList(start->successor);
        start->successor->successor = start;
        start->successor = nullptr;
        return newHead;
    }
};

The reasoning process for backward recursion can be simplified:

1. Assume the recursive call successfully reverses the sublist starting from the second node, yielding the new head.
2. The original head node remains linked to the now-final node of the reversed sublist. Redirect the final node's pointer back to the original head.
3. Terminate the original head's forward pointer to complete the local reversal, and propagate the new head upwards.

Distinguishing NULL and nullptr

In C++, NULL is historically defined as integer zero. While it implicitly converts to a null pointer, its integral nature causes unexpected behavior during function overload resolution.

Introduced in C++11, nullptr is a dedicated keyword of type std::nullptr_t. It exclusively represents a null pointer and cannot be implicitly converted to an integer.

Consider the following overloaded functions:

#include <iostream>

void process(int num) {
    std::cout << "Integer overload triggered: " << num << std::endl;
}

void process(char* ptr) {
    std::cout << "Pointer overload triggered." << std::endl;
}

int main() {
    process(NULL);    // Resolves to the integer overload, which is typically unintended
    process(nullptr); // Correctly resolves to the pointer overload
    return 0;
}

Passing NULL invokes the integer overload due to its underlying type, leading to logic errors when a pointer variant is expected. Utilizing nullptr eliminates this ambiguity by strictly matching pointer parameters.