day03 - 链表part01

力扣203. 移除链表元素

没有难度，只需掌握一个思路，即因为每次删除元素时，我们需要该元素的前一个元素的指针来操作，那么如果删除第一个元素呢？他的前一个元素无法获取因此需要进行特殊处理，而我们可以设置一个虚拟节点作为头结点，这样链表的每个元素的处理方式就统一了。

代码如下

ListNode* removeElements(ListNode* head, int val) {
    //设置虚拟头结点
    ListNode* dummyHead = new ListNode(0, head);
    //遍历的当前节点
    ListNode* cur = dummyHead;
    while (cur->next)
    {
        if (cur->next->val == val)
        {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        }
        else
        {
            cur = cur->next;
        }
    }
    return dummyHead->next;
}

力扣707. 设计链表

思路还是一样，利用虚拟头结点统一逻辑处理方式，难点在于太复杂了，边界值不清晰，照着答案都得改半天。

代码如下：

class MyLinkedList {
public:
    //定义节点结构体
    struct LinkedNode{
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };
    
    MyLinkedList() {
        dummyHead_  = new LinkedNode(0); 
        size_ = 0;
    }
    //返回index，此时index从0开始
    int get(int index) {
        if (index < 0 || index > (size_ - 1))
        {
            return -1;
        }
        LinkedNode* cur = dummyHead_->next;
        while (index--)
        {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = dummyHead_->next;
        dummyHead_->next = newNode;
        size_++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyHead_;
        while (cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = newNode;
        size_++;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size_)
        {
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyHead_;
        while(index--)
        {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        size_++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size_)
        {
            return;
        }
        LinkedNode* cur = dummyHead_;
        while(index--)
        {
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size_--;
    }
private:
    int size_;
    LinkedNode* dummyHead_;
};
​
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

力扣206. 反转链表

思路：因为每次反转时候后面的链表就会丢失，因此先定义一个tmp指针保存后面的链表，然后用双指针逐个反转。

代码

ListNode* reverseList(ListNode* head) {
    ListNode* tmp;
    ListNode* cur = head;
    ListNode* pre = nullptr;
    while (cur)
    {
    tmp = cur->next;
    cur->next = pre;
    pre = cur;
    cur = tmp;
    }
    return pre;
}