链表|203.移除链表元素、707.设计链表、206.反转链表

203.移除链表元素

自己审题思路

移除链表元素，需要拿到移除元素的前一个Node地址

看完代码随想录题解后的收获

链表操作，特别是链表删除操作，建立一个虚拟节点指向头结点会很方便(否则需要考虑删除的是否是头结点)。

代码：

/*
struct ListNode {
  int val;
  ListNode*  next;
  ListNode(int val) : val(val), next(nullptr) {}
};*/
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) return head;
        ListNode* dummyNode = new ListNode();
        dummyNode->next = head;
        ListNode* cur = dummyNode;
        while (cur->next) {
            if (cur->next->val == val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }

        }
        return dummyNode->next;
    }
};

参考详解

707.设计链表

自己审题思路

考察具体的链表操作，其中有一些细节需要注意

看完代码随想录题解后的收获

这道题覆盖了链表的常见操作，是练习链表操作非常好的一道题
其中细节比较容易犯错，借着这道题debug了一遍代码，算是为后续代码debug开个头

能够debug的代码：

// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include<iostream>

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=707 lang=cpp
 *
 * [707] 设计链表
 */

// @lc code=start


class MyLinkedList {
public:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int val) : val(val), next(nullptr) {}
        ListNode(int val, ListNode* next) : val(val), next(next) {}
    };

    MyLinkedList() {
        dummyNode = new ListNode(-1);
        size = 0;
    }
    
    int get(int index) {
        if (index > (size - 1) || index < 0) return -1;
        ListNode* cur = dummyNode->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }
    
    /* void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        ListNode* cur = dummyNode;
        cur->next = newNode;         //错误写法，没有将newNode->next定义，每次给链表头插入元素之后，之前添加的元素就丢失了
        size++;
    } */
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = dummyNode->next;
        dummyNode->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        ListNode* newNode = new ListNode(val);
        ListNode* cur = dummyNode;
        int x = size;
        while (x--) {// 之前这里使用的size--，错误，不能将size值改变！！！
            cur = cur->next;
        }
        cur->next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        ListNode* newNode = new ListNode(val);
        ListNode* cur = dummyNode;
        while (index--) {
            cur = cur->next;
        }
        ListNode* temp = cur->next;
        cur->next = newNode;
        newNode->next = temp;
/*         newNode->next = cur->next;
        cur->next = newNode; */
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index >= size || index < 0) return;
        ListNode* cur = dummyNode;
        ListNode* temp;
        while (index--) {
            cur = cur->next;
        }
        temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp = nullptr;
        
        size--;
    }

    void printLinkedList() {
        ListNode* cur = dummyNode;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
        system("pause");
    }

private:
    ListNode* dummyNode;
    int size; 
};

int main () {
    MyLinkedList* myLinkedList = new MyLinkedList();
    myLinkedList->addAtHead(1);
    myLinkedList->addAtHead(3);
    myLinkedList->addAtHead(1);
    // myLinkedList->addAtTail(3);
    myLinkedList->addAtIndex(3, 0); 
    myLinkedList->printLinkedList();
    myLinkedList->addAtIndex(1, 2);    
    myLinkedList->printLinkedList();
    myLinkedList->get(1);           
    myLinkedList->printLinkedList();
    myLinkedList->deleteAtIndex(1);  
    myLinkedList->printLinkedList();
    cout << myLinkedList->get(1) << endl;

    return 0;
}
/* int main () {
    MyLinkedList* myLinkedList = new MyLinkedList();
    myLinkedList->addAtHead(1);
    myLinkedList->addAtTail(3);
    myLinkedList->printLinkedList();
    myLinkedList->addAtIndex(1, 2);    // 链表变为 1->2->3
    myLinkedList->printLinkedList();
    myLinkedList->get(1);              // 返回 2
    myLinkedList->printLinkedList();
    myLinkedList->deleteAtIndex(1);    // 现在，链表变为 1->3
    myLinkedList->printLinkedList();
    cout << myLinkedList->get(1) << endl;              // 返回 3

    return 0;
} */

如果将ListNode* dummyNode定义在结构体struct ListNode之前，在编译时就会出现以下报错：
error: incompatible pointer types assigning to 'ListNode *' from 'MyLinkedList::ListNode *'
new ListNode(-1) 是MyLinkedList::ListNode *类型，而 dummyNode被识别成了ListNode *类型，因为在类MyLinkedList定义struct ListNode之前就定义了 dummyNode。

4070d4cf0f962addb13c89dcdedeb00.png

参考详解

206.反转链表

自己审题思路

经典题，双指针，将后一个节点指向前一个节点

看完代码随想录题解后的收获

利用双指针的思路写出递归版本代码

双指针代码：

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

递归版本代码：

class Solution {
public:
    ListNode* reverse(ListNode* pre, ListNode*cur) {
        if(cur == nullptr) return pre;
        ListNode* tmp = cur->next;
        cur->next = pre;
        return reverse(cur, tmp);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }
};

参考详解

今日感想：

1、代码隐藏的bug还是需要好好debug看看变量的变化过程；
2、还是要加强C++语法的熟悉。