Day3虚拟头指针，设计链表，反转链表

By HQWQF 2023/12/15

笔记

203.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

解法：虚拟头指针

看起来非常简单，但是由于如果直接对原始的链表进行操作，如果头节点的val属性就等于val，那么我们需要删除头节点，而删除头节点和删除其他节点的过程是不一样的，我们通常用cur->next->val == val;这个语句来判断cur->next是否需要删除，而对则头节点无法这样操作。

如果我们使用虚拟头节点的技巧，在头节点前人为设置一个虚拟头节点，让循环判断从虚拟头节点开始，我们就可以在所有节点（当然除了虚拟头节点）使用同样的处理了。

class Solution {
public:
    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;//删除tmp所指的节点
            } else 
            {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;//删除虚拟节点
        return head;
    }
};

注释：

使用C/C++编程语言的话，记得要把移除的节点和new 出来的虚拟头结点从内存中删除，delete 指向需要删除的地址的指针。

707.设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

解法：数据结构的基础知识

不要搞错这些链表的基础操作就行。

删除某个节点：

//删除tmp的下一个节点
LinkedNode* toDelete = tmp->next;
tmp->next = toDelete->next;
delete toDelete;
_size--;

增加个节点：

//tmp后增加一个节点
LinkedNode* newNode = new LinkedNode(val);
newNode->next = tmp->next;
tmp->next = newNode;

完整代码：

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

    MyLinkedList() {
        _size = 0;
        _dummyHead = new LinkedNode(0);
    }
    int get(int index) {
        if (index > _size-1 || index < 0) { return -1; }
        LinkedNode* tmp = _dummyHead->next;
        for (size_t i = 0; i < index; i++)
        {
            tmp = tmp->next;
        }
        return tmp->val;
    }
    void addAtHead(int val) {
        LinkedNode* tmp = new LinkedNode(val);
        tmp->next = _dummyHead->next;
        _dummyHead->next = tmp;
        _size++;
    }
    void addAtTail(int val) {
        LinkedNode* tmp = _dummyHead;
        while (tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        LinkedNode* newNode = new LinkedNode(val);
        tmp->next = newNode;
        _size++;
    }
    void addAtIndex(int index, int val) {
        LinkedNode* tmp = _dummyHead;
        if (0 <= index && index <= _size)
        {
            for (size_t i = 0; i < index; i++)
            {
                tmp = tmp->next;
            }
            LinkedNode* newNode = new LinkedNode(val);
            newNode->next = tmp->next;
            tmp->next = newNode;
            _size++;
        }
        
    }
    void deleteAtIndex(int index) {
        if (0 <= index && index <= _size-1)
        {
            LinkedNode* tmp = _dummyHead;
            for (size_t i = 0; i < index; i++)
            {
                tmp = tmp->next;
            }
            LinkedNode* toDelete = tmp->next;
            tmp->next = toDelete->next;
            delete toDelete;
            //delete命令指示释放了toDelete指针原本所指的那部分内存，
            //被delete后的指针toDelete的值（地址）并非就是NULL，而是随机值。也就是被delete后，
            //如果不再加上一句toDelete=nullptr,toDelete会成为乱指的野指针
            //如果之后的程序不小心使用了toDelete，会指向难以预想的内存空间
            toDelete = nullptr;
            _size--;
        }
    }
private:
    int _size;
    LinkedNode* _dummyHead;
};

注释：

delete tmp后，tmp并非就是NULL，而是随机值，所以我们需要在delete tmp后将tmp= nullptr;

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法：双指针法，递归法

第一时间比较容易想到的是要使用3个指针变量，因为在单链表里，如果只有当前节点和前一个节点，在把当前节点的next指向前一个节点后，当前节点的下一个节点就会丢失。

        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;

另外，我们需要一个循环来遍历链表，将代表当前节点的指针不断移动。现在的一个问题是循环的结束条件是哪个指针，这个问题要和返回3个指针的哪一个这个问题联系起来。首先考虑边界情况，如果用pre ≠ NULL，在遍历到链表尾时cur 会为NULL需要另外处理，如果用temp≠ NULL，由于在没节点的情况下，需要另外处理，所以我们的循环条件用cur，当cur不成立时，需要返回的是pre。

双指针法完整代码

class Solution {
public:
ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    ListNode* cur = head;
     ListNode* temp;
    while (cur) {
        ListNode* temp = cur->next; // 保存cur的下一个节点
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    
    return pre;
}
};

另外我们也可以用递归法，从前向后每次reverse()处理一对节点。

递归法，从从前向后

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

还有一种从后向前的递归法，是比较典型的递归思维，只要把由第二个节点后的子链表逆转，再把前两个节点反转即可。

递归法，从从后向前

class Solution {
public:
    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;
    }
};

标签：tmp,cur,val,Day3,next,链表,节点,指针
From： https://www.cnblogs.com/HQWQF/p/17904287.html

算法学习Day3虚拟头指针，设计链表，反转链表