移除链表元素

可能出现两个val一样的在一起，所以使用while循环

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 双指针 一个虚节点
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* pre = new ListNode(0, head);
        ListNode* dummy = pre;
        while(head != nullptr)
        {
            while(head != nullptr && head->val == val)
            {
                head = head->next;
            }
            pre->next = head;
            pre = head;
            if(head != nullptr) head = head->next;
        }
        return dummy->next;
    }
};

707. 设计链表

直接用的单链表，类名不能重复

// 节点 : 单链表
class DListNode {
public:
    DListNode(int val_) : val(val_), next(nullptr) {}
    int val;
    DListNode* next; 
};

class MyLinkedList {
public:
    MyLinkedList() {
        this->head = new DListNode(0); // 虚拟头结点
        head->next = nullptr;
    }

    int get(int index) {
        DListNode* work = new DListNode(0);
        work = head->next;
        while(index --)
        {
            if (work == nullptr) return -1;
            work = work->next;
        }
        if (work == nullptr) return -1;
        return work->val;
    }

    void addAtHead(int val) {
        DListNode* tmp = new DListNode(val);
        tmp->next = head->next;
        head->next = tmp;
    }

    void addAtTail(int val) {
        DListNode* pre = head;
        while (pre->next != nullptr)
            pre = pre->next;
        DListNode* tmp = new DListNode(val);
        tmp->next = pre->next;
        pre->next = tmp;
    }

    void addAtIndex(int index, int val) {
        DListNode* pre = head;
        for (int i = 0; i < index; i ++)
        {
            if (pre != nullptr)
                pre = pre->next;
            else
                return;
        }
        if (pre == nullptr) return;
        DListNode* tmp = new DListNode(val);
        tmp->next = pre->next;
        pre->next = tmp;        
    }

    // 前后双指针
    void deleteAtIndex(int index) {
        DListNode* pre = head;
        DListNode* work = head->next;
        for (int i = 0; i < index; i ++)
        {
            if (work == nullptr) return;
            pre = work;
            work = work->next;
        }
        if (work == nullptr) return;
        pre->next = work->next;
        delete work;
    }

private:
    DListNode *head;
};

206. 反转链表

用的前后指针，注意点是前面的指针初始值要是nullptr

class Solution {
public:
    // 最简单的办法就是前后双指针
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* work = head;
        ListNode* next = new ListNode;
        while(work != nullptr)
        {
            next = work->next;
            work->next = pre;
            pre = work;
            work = next;
        }
        return pre;
    }
};