Linked List Fundamentals

Linked lists consist of nodes connected via pointers, differing from arrays in their non-contiguous memory allocation. Common variants include singly-linked, doubly-linked, and circular linked lists.

A basic singly-linked list node structure in C++:

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int x) : value(x), next(nullptr) {}
};

Removing Elements from a Linked List

Given a linked list head and a target value, remove all nodes containing that value and return the modified list.

Example:

• Input: head = [1,2,6,3,4,5,6], val = 6
• Output: [1,2,3,4,5]

Solution using dummy head node:

class Solution {
public:
    ListNode* removeElements(ListNode* head, int target) {
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode* current = sentinel;
        
        while (current->next != nullptr) {
            if (current->next->value == target) {
                ListNode* toDelete = current->next;
                current->next = current->next->next;
                delete toDelete;
            } else {
                current = current->next;
            }
        }
        
        head = sentinel->next;
        delete sentinel;
        return head;
    }
};

The dummy head approach simplifies edge cases by providing a consistent starting point.

Implementing a Linked List Class

Design a linked list class supporting these operations:

• get(index) - Retreive value at index
• addAtHead(val) - Insert at beginning
• addAtTail(val) - Append at end
• addAtIndex(index, val) - Insert at specific position
• deleteAtIndex(index) - Remove at index

Implemantation:

class MyLinkedList {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) : data(val), next(nullptr) {}
    };
    
    Node* dummyHead;
    int length;
    
public:
    MyLinkedList() {
        dummyHead = new Node(0);
        length = 0;
    }
    
    int get(int position) {
        if (position < 0 || position >= length) return -1;
        
        Node* current = dummyHead->next;
        for (int i = 0; i < position; i++) {
            current = current->next;
        }
        return current->data;
    }
    
    void addAtHead(int value) {
        Node* newNode = new Node(value);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        length++;
    }
    
    void addAtTail(int value) {
        Node* newNode = new Node(value);
        Node* current = dummyHead;
        
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
        length++;
    }
    
    void addAtIndex(int position, int value) {
        if (position > length) return;
        if (position < 0) position = 0;
        
        Node* newNode = new Node(value);
        Node* current = dummyHead;
        
        for (int i = 0; i < position; i++) {
            current = current->next;
        }
        
        newNode->next = current->next;
        current->next = newNode;
        length++;
    }
    
    void deleteAtIndex(int position) {
        if (position < 0 || position >= length) return;
        
        Node* current = dummyHead;
        for (int i = 0; i < position; i++) {
            current = current->next;
        }
        
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
        length--;
    }
};

Reversing a Linked List

Reverse a singly-linked list in-place.

Iterative approach:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* previous = nullptr;
        ListNode* current = head;
        
        while (current != nullptr) {
            ListNode* nextTemp = current->next;
            current->next = previous;
            previous = current;
            current = nextTemp;
        }
        
        return previous;
    }
};

Recursive approach:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        ListNode* reversed = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        
        return reversed;
    }
};

The recursive method reverses the list by recursively processing subsequent nodes before modifying the current node's pointers.