代码随想录算法训练营Day03 | LeetCode203 移除链表元素、LeetCode707 设计链表、LeetCode206 反转链表

今日学习的视频和文章

• 代码随想录 链表基础
• 代码随想录 移除链表元素
• 代码随想录 设计链表
• 代码随想录 反转链表

LeetCode203 移除链表元素

203. 移除链表元素 - 力扣（Leetcode）

• 初见题目的想法：用temp指向上一个节点，cur保留当前节点，如果cur指向的节点为目标值，则将temp->next。
  • 没有考虑头节点也为目标值的情况。在复习链表知识后，我发现对链表节点的操作，往往要考虑头节点和非头节点的两种情况。如果head保存的是真正的头节点，那么操作链表节点时要考虑当前操作的节点是否是head指向的节点，是否会影响头节点。
  • 对于头节点的操作和非头节点的操作往往是不一样的。比如删除非头节点，只需要让cur->next指向cur->next->next即可，而删除头节点时，还要注意让head指向新的头节点。

完整题解代码如下：

ListNode* removeElements(ListNode* head, int val) {
    while (head != NULL && head->val == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }

    ListNode* cur = head;
    while (cur != NULL && cur->next != NULL) {
        if (cur->next->val == val) {
            ListNode* temp = cur->next;
            cur->next = cur->next->next;
            delete temp;
            continue;
        }
        cur = cur->next;
    }
    return head;
}

• 所以，虚拟头节点dummyHead是很有必要的。引入虚拟头节点最直观的优势就是可以将对头节点和非头节点的操作统一起来，让代码逻辑更加简单，实现更加容易。

引入虚拟头节点的题解代码：

ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummyHead = new ListNode(INT_MIN);
    dummyHead->next = head;
    ListNode* cur = dummyHead;
    while (cur->next != NULL) {
        if (cur->next->val == val) {
            ListNode* del = cur->next;
            cur->next = cur->next->next;
            delete del;
        }
        else {
            cur = cur->next;
        }
    }
    head = dummyHead->next;
    delete dummyHead;//记得释放虚拟头节点的空间，有 new，要记得 delete
    return head;
}

LeetCode707 设计链表

707. 设计链表 - 力扣（Leetcode）

• 不使用虚拟头节点的话，每个有可能操作虚拟头节点的函数都要考虑头节点和非头节点两种情况，之后我会补上不使用虚拟头节点的单向链表的代码和使用虚拟头节点的进行比较。
• 使用虚拟头节点，就可以把对头节点和非头节点的操作统一起来。因为有一个“不变的”虚拟头节点，所以我们只需要考虑如何操作非头节点即可。

完整的题解代码，以及一些写在注释里的理解

class MyLinkedList {
    struct linkedNode {
        int val;
        linkedNode* next;
        linkedNode(int val) : val(val), next(nullptr) {}
    };
private:
    linkedNode* dummyHead;
    int size;
public:
    MyLinkedList() : size(0) {
        dummyHead = new linkedNode(-1);
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        else {
            linkedNode* cur = dummyHead->next;
            // cur 指向 dummyHead 还是 dummyHead->next 是与 while 的条件对应的
            // 这里的 index 可以理解为：cur 从指向头节点开始，向后移动的次数
            while (index--) {
                cur = cur->next;
            }
            return cur->val;
        }
    }
    
    void addAtHead(int val) {
        // 这里体现使用虚拟头节点的好处，虚拟头节点是“不动的”，虚拟头节点的 next 始终保存着真正的头节点
        // 只需要让 newNode 的 next 指向原来头节点，然后让虚拟头节点的 next 指向 newNode
        linkedNode* newNode = new linkedNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        // 这里要考虑链表为空的情况，所以让 cur 指向虚拟头节点
        // 链表为空时虚拟头节点的 next 就是要插入的位置
        linkedNode* cur = dummyHead;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        linkedNode* newNode = new linkedNode(val);
        cur->next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        // 这里要注意，由于可以在尾部插入，所以 index 可以等于 size
        if (index < 0 || index > size) {
            return;
        }
        linkedNode* cur = dummyHead;
        while (index--) {
            cur = cur->next;
        }
        linkedNode* newNode = new linkedNode(val);
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        // 而这里 index 最大取到 size - 1，所以这里直接return的条件要取等号
        if (index < 0 || index >= size) {
            return;
        }
        linkedNode* cur = dummyHead;
        while (index--) {
            cur = cur->next;
        }
        cur->next = cur->next != nullptr ? cur->next->next : nullptr;
        size--;
    }
};

/**
 * 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);
 */

LeetCode206 反转链表

• 初见题目的想法：使用pre指针指向cur的上一个节点，cur指向当前节点，next保存cur的下一个节点。
  • 犯的错误：没有考虑清楚原本的头节点如何反转，其实这里也可以用虚拟头节点的思想来解决，头节点的next的反转后应该指向NULL那么这个NULL就可以作为头节点的pre，来统一头节点和非头节点的操作。
  • 另外，由于反转后，最后一个节点就变成了头节点，这里也要考虑如何操作头节点。最后一个节点反转后就是head，且没有其他节点的next指向它。对于最后一个节点，就是反转了它的next，但不用再让其下一个节点的next指向它。

完整题解代码如下：

ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    head = pre;//注意这里不是 head = cur，pre 指向的才是完成了反转的节点，而 cur 指向的应该是等待被反转的当前节点
    return head;
}