linked_list.hpp

Go to the documentation of this file.

#ifndef LINKED_LIST_H
#define LINKED_LIST_H
 
#include <vector>
 
namespace hsc_snippets {
    struct ListNode {
        int val;
        ListNode *next;
 
        ListNode() : val(0), next(nullptr) {
        }
 
        explicit ListNode(int x) : val(x), next(nullptr) {
        }
 
        ListNode(int x, ListNode *next) : val(x), next(next) {
        }
    };
 
    static int get_linked_list_length(ListNode *head) {
        int len = 0;
        while (head != nullptr) {
            len += 1;
            head = head->next;
        }
        return len;
    }
 
    static ListNode *make_linked_list(const std::vector<int> &v) {
        if (v.empty()) {
            return nullptr;
        }
        auto head = new ListNode;
        ListNode *prev = nullptr;
        auto it = v.begin();
        while (it != v.end()) {
            if (prev == nullptr) {
                head->val = *it;
                prev = head;
            } else {
                prev->next = new ListNode(*it);
                prev = prev->next;
            }
            it = std::next(it);
        }
 
        return head;
    }
 
    static std::vector<int> linked_list_to_vector(ListNode *head) {
        auto v = std::vector<int>{};
        while (head != nullptr) {
            v.push_back(head->val);
            head = head->next;
        }
        return v;
    }
 
    static void linked_list_delete(ListNode *head) {
        if (head == nullptr) {
            return;
        }
        auto next = head->next;
        while (next != nullptr) {
            delete head;
            head = next;
            next = head->next;
        }
        delete head;
    }
 
    static ListNode *linked_list_remove(ListNode *head, size_t begin, size_t end) {
        if (head == nullptr || begin >= end) {
            // Nothing to remove
            return head;
        }
 
        ListNode dummy(0, head); // Create a dummy node to simplify edge cases
        ListNode *prev = &dummy;
 
        // Move `prev` to the node just before `begin`
        for (size_t i = 0; i < begin && prev->next != nullptr; ++i) {
            prev = prev->next;
        }
 
        ListNode *current = prev->next;
 
        // Remove nodes in range [begin, end)
        for (size_t i = begin; i < end && current != nullptr; ++i) {
            ListNode *temp = current;
            current = current->next;
            delete temp; // Free the removed node
        }
 
        // Connect the node before `begin` to the node at `end`
        prev->next = current;
 
        return dummy.next; // Return the new head, which is the next of dummy node
    }
 
 
    static ListNode *get_linked_list_ith_node(ListNode *head, size_t i) {
        size_t current_index = 0;
        while (head != nullptr) {
            if (current_index == i) {
                return head;
            }
            head = head->next;
            current_index++;
        }
        return nullptr; // Index out of bounds
    }
}
 
#endif // LINKED_LIST_H