「代码随想录算法训练营」第三天 | 链表 part1

203.移除链表元素

题目链接:https://leetcode.cn/problems/remove-linked-list-elements/
题目难度:简单
文章讲解:https://programmercarl.com/0203.移除链表元素.html
视频讲解: https://www.bilibili.com/video/BV18B4y1s7R9
题目状态:通过

个人思路:

从链表头部开始依次往下遍历,当遇到和val值相等的元素就将其移除(walk->next = walk->next->next),最后返回修改后的链表。

遇到的问题:

  1. 直接将遍历指针walk初始化在了链表头,没能考虑到头节点就是需要移除的节点的情况。
  2. 采用 C++ 编写代码的时候,忘记要从内存中删除移除的节点,清理节点内存

最终代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while(head != nullptr && head->val == val)
        {
            head = head->next;
        }

        ListNode *dummy = new ListNode(0);
        dummy->next = head;

        ListNode* walk = dummy;
        while(walk->next != nullptr)
        {
            if(walk->next->val == val)
            {
                ListNode *tmp = walk->next;
                walk->next = tmp->next;
                delete tmp;
            }
            else
            {
                walk = walk->next;
            }
        }
        ListNode *newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

707.设计链表

题目链接:https://leetcode.cn/problems/design-linked-list/
题目难度:中等
文章讲解:https://programmercarl.com/0707.设计链表.html
视频讲解: https://www.bilibili.com/video/BV1FU4y1X7WD
题目状态:思路混乱,看卡哥代码

最终代码如下:

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

    MyLinkedList() {
        _dummyHead = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if(index >= _size || index < 0) return -1;
        LinkedNode *cur = _dummyHead->next;
        while(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++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        if(index < 0) index = 0;

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

    }
    
    void deleteAtIndex(int index) {
        if(index >= _size || index < 0) return;
        LinkedNode *cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        LinkedNode *tmp = cur->next;
        cur->next = tmp->next;
        delete tmp;
        tmp = nullptr;
        _size--;
    }
private:
    int _size;
    LinkedNode *_dummyHead;
};

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

⚠️注意:

deleteAtIndex接口中使用delete释放了tmp指针原本所指的那部分内存,但是被delete后的指针tmp的值并不是nullptr,而是随机值,即tmp成为了野指针,因此需要将tmp = nullptr

206.反转链表

题目链接:https://leetcode.cn/problems/reverse-linked-list/
题目难度:简单
文章讲解:https://programmercarl.com/0206.翻转链表.html
视频讲解: https://www.bilibili.com/video/BV1nB4y1i7eL
题目状态:通过

个人思路:

构建一个新链表用于存储反转后的链表,再循环旧的链表,每循环到一个节点,就将该节点的值采用头插法插入到新链表中,最后返回新链表。

实现代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return head;

        ListNode *newList = new ListNode();
        ListNode *cur = head;
        while(cur != nullptr) {
            ListNode *tmp = new ListNode(cur->val);
            tmp->next = newList->next;
            newList->next = tmp;
            cur = cur->next;
        }
        return newList->next;
    }
};

过是过了,但看着那两个大大的new并且没有delete我就恶心,感觉自己又写了一坨……

其他思路:

1. 双指针法

a. 直接定义两个指针curprecur用于遍历,pre用于保存cur的前一个节点。
b. 每次遍历到下一个节点的时候,cur就会将它的下一个节点的指向指到自己的前一个节点pre,最后更新自己到原本的下一个节点。

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return head;

        ListNode *cur = head;
        ListNode *pre = nullptr;
        ListNode *tmp;
        while(cur != nullptr) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

2. 递归法

思路和双指针法相同,代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }
    ListNode *reverse(ListNode *pre, ListNode *cur) {
        if(cur == nullptr) 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;
    }
}; 

热门相关:命令小妈妈   邪王追妻99次:娘子,等我   美漫大幻想   帝少夜宠:小甜妻,乖!   我老婆的姐姐2