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

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

LeetCode 203.移除链表元素
LeetCode 707.设计链表
LeetCode 206.反转链表
- 双指针法
- 递归法

LeetCode 203.移除链表元素

注意，在dummy上操作，返回也返回dummy->next
如果头铁想返回head，那样会发现head没有变化
因为实际上dummy->next和head并不是同一块地址空间的内容
函数里的操作改变的都是新的dummy节点上进行的
原始链表的连接关系没有改变

    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre= dummy;
        ListNode* cur = dummy->next;
        while(cur != NULL){
            if(cur->val == val){
                pre->next = cur->next;
                cur = pre->next;
            }else{
                //这个else是后面补的，原先没写else出了一堆问题，还又增加了if分支
                cur=cur->next;
                pre=pre->next;
            }
        }
        return dummy->next;
    }

因为一个else卡了半天查呀查呀查
是我没有想到的
如果不写else问题很大，那样这里要加一个判断，再判断是否cur为空
这还不够，不写else如果上面if内部执行了，就不能再往下推进pre和cur，这也是为啥要写else
不是很难想的逻辑，但是第一遍写代码甚至好几遍检查的时候都没有查出来这个点，思维还是混乱
这道题21年也写过通过了
ok接下来看看卡哥的

链表操作中，可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点再进行删除操作，接下来看一看哪种方式更方便。
21年的代码相当于前者，今天的代码相当于后者

卡哥说：还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。
这个我没有写

那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？
这里就涉及如下链表操作的两种方式：
（1）直接使用原来的链表来进行删除操作。

 ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;}
        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {cur = cur->next;}}
        return head;
    }

（2）设置一个虚拟头结点在进行删除操作。

ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {cur = cur->next;}}
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }

附：和鸡皮题的对线记录

鸡皮题：实际上，dummy->next 和 head 在这段代码中并不是同一块地址空间的内容。在函数中的操作并没有改变原始链表中的节点的连接关系，而是在新的dummy节点上进行操作，因此返回的结果应该为dummy->next 而不是 head。
当你在函数返回 dummy->next 时，实际上是返回了经过修改后的链表头。原始的 head 节点并没有发生改变，因为你在操作链表时只是在 dummy 节点上进行的连接修改。
如果你想改变原始链表的头节点，可以修改函数的返回类型为 ListNode* & 或者使用引用类型进行传参，并在函数中通过修改传入的引用参数来修改原链表头节点。
我：但没有引用类型，head传过去的也是一个实际的内存地址啊
（心里确实有这样的疑惑，因为和我的常识不符）
鸡皮题：在C++中，虽然我们传递指针或者引用参数时是传递的地址，但在函数内部进行的指针或引用的指向修改，并不影响原始指针或引用的指向。因此，在函数内部操作的数据只是在函数内部生效，不会影响原始数据的内容。所以，你在上述代码中对链表进行的操作并没有修改原始链表的连接关系，所以返回的是原始链表头节点的地址。
如果你想修改原始链表，可以通过引用传递一个指向链表头节点的指针或者引用，在函数内部通过修改传入的指针或引用来改变原始链表的内容。
我：地址指向的修改都不影响吗？
（常识是肯定是修改的啊，指针传参数，引用传参数，这是我的常识）
鸡皮题：地址指向的修改是影响的，但是在你的代码中，你只是通过改变pre->next指针的指向来实现删除节点的操作，并没有改变head指针本身的值。因此，虽然dummy->next和head初始时指向同一个节点，但是在函数执行过程中，只有dummy->next的指向发生了变化，而head指针本身并没有被修改。
如果你希望返回的是修改后的链表头节点，你可以在函数内部维护一个新的指针变量来记录新的头节点，然后在操作结束后返回这个新的头节点。这样就能返回修改后的链表了。

鸡皮题是这样把我说服的，确实应该是这个样子的，我倒腾的指针都没有去试图改变head本身
有这么一个模糊的抽象，但并不是很清晰，说明思维还是有些混乱

LeetCode 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是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--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++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        //delete命令指示释放了tmp指针原本所指的那部分内存，
        //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
        tmp=nullptr;
        _size--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};

今天有点上强度
现在有点困，明天又直接4道题+链表总结
这个强度是否有点太高了
准备休息了，梦里继续想
无所谓，我会开摆

LeetCode 206.反转链表

这个感觉还好，没有上个那么脑袋疼
但也不是一遍过的
最开始没有else break;陷入死循环了

    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur){
            ListNode* tmp = NULL;
            if(cur->next) tmp = cur->next;
            cur->next = pre;
            if(tmp){
                pre = cur;
                cur = tmp;
            }else break; 
        }
        return cur;
    }

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:
反转链表
之前链表的头节点是元素1，反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。

（1）首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
（2）然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
（3）为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
（4）接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
（5）最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。

双指针法

ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }

感觉相比之下我的代码有点瞎忙活
明明不用ifelse分支去判断的，我写了俩分支去判断
这里我的思路也不是很清晰

递归法

    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。

关键是初始化的地方，可能有的同学会不理解，可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。

具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。

我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。

 ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }