顺序表

class Vector {
public:
    Vector(int n) : size(n), count(0) {
        data = new int[size];
    }

    ~Vector() {
        delete[] data;
    }

    bool expand() {
        std::cout << "expand v from " << size << " to " << 2 * size << std::endl;
        int *p = new int[2 * size];
        if (p == nullptr) return false;
        for (int i = 0; i < count; ++i) {
            p[i] = data[i];
        }
        delete[] data;
        data = p;
        size *= 2;
        return true;
    }

    bool insert(int pos, int val) {
        if (pos < 0 || pos > count) return false;
        if (size == count && !expand()) return false;
        for (int i = count - 1; i >= pos; i--) {
            data[i + 1] = data[i];
        }
        data[pos] = val;
        ++count;
        return true;
    }

    bool erase(int pos) {
        if (pos < 0 || pos >= count) return false;
        for (int i = pos + 1; i < count; ++i) {
            data[i - 1] = data[i];
        }
        --count;
        return true;
    }

    void output() const {
        int len = 0;
        for (int i = 0; i < size; ++i) {
            len += std::printf("%3d", i);
        }
        std::cout << std::endl;
        for (int i = 0; i < len; ++i) std::cout << "-";
        std::cout << std::endl;
        for (int i = 0; i < count; ++i) {
            std::printf("%3d", data[i]);
        }
        std::cout << std::endl << std::endl;
    }

private:
    int size, count;
    int *data;
};

链表

#define DL 3
#define STR(n) #n
#define DIGIT_LEN_STR(n) "%" STR(n) "d"

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

class LinkedList {
public:
    LinkedList() : head(nullptr) {}    
    ~LinkedList() {
        clear();
    }

    void insert(int pos, int val) {
        Node dummy(0);
        dummy.next = head;
        Node *p = &dummy;
        Node *node = new Node(val);
        for (int i = 0; i < pos; i++) {
            if (p->next == nullptr) break;
            p = p->next;
        }
        node->next = p->next;
        p->next = node;
        head = dummy.next;
    }

    void clear() {
        Node *p = head;
        while (p != nullptr) {
            Node *q = p->next;
            delete p;
            p = q;
        }
        head = nullptr;
    }

    void output(int flag = 0) const {
        int n = 0;
        for (Node *p = head; p; p = p->next) n += 1;
        for (int i = 0; i < n; i++) {
            printf(DIGIT_LEN_STR(DL), i);
            printf("  ");
        }
        printf("\n");
        for (Node *p = head; p; p = p->next) {
            printf(DIGIT_LEN_STR(DL), p->data);
            printf("->");
        }
        printf("\n");
        if (flag == 0) printf("\n\n");
    }

    bool find(int val) const {
        Node *p = head;
        int n = 0;
        while (p) {
            if (p->data == val) {
                output(1);
                int len = n * (DL + 2) + 2;
                for (int i = 0; i < len; i++) printf(" ");
                printf("^\n");
                for (int i = 0; i < len; i++) printf(" ");
                printf("|\n");
                return true;
            }
            n += 1;
            p = p->next;
        }
        return false;
    }
private:
    Node *head;
};

Leetcode-206 反转链表

法一:迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode*temp;
        ListNode*cur=head;
        ListNode *pre=nullptr;
        while(cur){
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
};

法二:递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode*tail=head->next;
        ListNode*newhead=reverseList(head->next);
        tail->next=head;
        head->next=nullptr;//最后断开头节点与Tail的联系
        return newhead;
    }
};

Leetcode-141 环形链表

快慢指针:

class Solution {
public:
    bool hasCycle(ListNode *head) {
       if(head==nullptr||head->next==nullptr)return false;
       ListNode*slow=head;
       ListNode*fast=head->next;
       while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true; 
    }
};

Leetcode-202 快乐数

class Solution {
public:
    int getnext(int x){
        int d,y=0;
        while(x){
            d=x%10;
            y+=d*d;
            x/=10;
        }
        return y;
    }
    bool isHappy(int n) {
        int p=n,q=n;
        while(q!=1){
            p=getnext(p);
            q=getnext((getnext(q)));
            if(p==q&&p!=1)return false;
        }
        return true;
    }
};

Leetcode-61 旋转链表

class Solution {
public:
    int getlength(ListNode* head) {
        int n = 0;
        while (head) {
            head = head->next;
            n += 1;
        }
        return n;
    }
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL) return head;
        int n = getlength(head);
        k %= n;
        if (k == 0) return head;
        ListNode *p = head, *q = head;
        k++;
        while(k--) p = p->next;
        while (p) p = p->next, q = q->next;
        p = q->next;
        q->next = NULL;
        q = p;
        while (q->next != NULL) q = q->next;
        q->next = head;
        return p;
    }
};

Leetcode-19 删除链表的倒数第 N 个结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*newhead=new ListNode(0);
        newhead->next=head;
        ListNode*p=newhead;
        ListNode*q=head;
        while(n--)q=q->next;
        while(q){
            p=p->next;
            q=q->next;
        }
        p->next=p->next->next;
        return newhead->next;
    }
};

Leetcode-142 环形链表 II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode*fast=head;
        ListNode*slow=head;
        while(fast!=NULL&&fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast){
                ListNode*p1=head;
                ListNode*p2=slow;
                while(p1!=p2){
                    p1=p1->next;
                    p2=p2->next;
                }
                return p1;
            }
        }
        return nullptr;
    }
};

Leetcode-92 反转链表 II

递归:

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left==1&&right==1)return head;
        if(left!=1){
            head->next=reverseBetween(head->next,left-1,right-1);
        }
        else{
            ListNode*tail=head->next;
            ListNode*newhead=reverseBetween(head->next,left,right-1);
            head->next=tail->next;
            tail->next=head;
            head=newhead;            
        }
        return head;
    }
};