526互联

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

发布时间 2023-12-15 22:23:02作者: HQWQF

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;
    }
};