day03 移除链表元素设计链表反转链表

2024-01-03 15:51:12

题目1：203 移除链表元素

题目链接：203 移除链表

题意

删除链表中所有满足Node.val==val的节点? ?返回新的头节点

注意使用cur临时指针，遍历链表，这样才可以最终返回head，不可以拿着head去遍历，否则，头节点会改变，无法返回整个链表

分类讨论

代码

/**
 * 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!=NULL && head->val==val){
            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;
    }
};

时间复杂度: O(n)
空间复杂度: O(1)

虚拟头节点

本题使用虚拟头节点方法? 更优，这样不用分类讨论，可以统一操作

代码

/**
 * 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) {
        //定义虚拟头节点
        ListNode *dummyhead = new ListNode(0);
        dummyhead->next = head;
        //定义临时指针cur,遍历链表
        ListNode *cur = dummyhead;
        //遍历所有的链表节点
        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 dummyhead->next;//注意返回的dummyhead一定是新链表的头节点
    }
};

时间复杂度: O(n)
空间复杂度: O(1)

题目2：707 设计链表

题目链接：707 设计链表

题意

链表实现如下功能：

①初始化节点

②获取链表的某个节点值? （index从0开始，head的index为0）

③在头节点前面插入一个节点

④在尾节点后面插入一个节点

⑤在第n个节点处插入一个节点

⑥删除第n个节点

代码

①初始化节点

//定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val),next(nullptr){}  //没有分号
        
    };
    //初始化链表
    MyLinkedList() {
        dummyhead = new LinkedNode(0);
        size_ = 0;   
    }

②获取链表的某个节点值? （index从0开始，head的index为0）

法1：cur指向dummyhead

代码1

int get(int index) {
        if(index<0 || index>(size_-1)) return -1;
        LinkedNode* cur = dummyhead;
        while(index){
            cur = cur->next;
            index--;
        }
        return cur->next->val;   
    }

法2：cur指向dummyhead->next

代码2

int get(int index) {
        if(index<0 || index>(size_-1)) return -1;
        LinkedNode* cur = dummyhead->next;
        while(index){
            cur = cur->next;
            index--;
        }
        return cur->val;   
    }

③在头节点前面插入一个节点

注意插入的节点顺序，这非常关键，这也是“坑”

代码

 void addAtHead(int val) {
        LinkedNode* newnode = new LinkedNode(val);
        newnode->next = dummyhead->next;
        dummyhead->next = newnode;
        size_ ++;//注意添加了元素，要在原链表的基础上加1
    }

④在尾节点后面插入一个节点

注意while循环的条件是cur->next!=NULL 不能是size_

代码

void addAtTail(int val) {
        LinkedNode* cur = dummyhead;
        LinkedNode* newnode = new LinkedNode(val);
        while(cur->next!=nullptr){
            cur = cur->next;
        }
        cur->next = newnode;
        size_++;//添加了元素，链表大小加1
    }

！！！错误代码（如果使用size_做循环操作，那么意味着表示链表大小的量size_会发生变化，不能拿代表真实的链表大小了）

void addAtTail(int val) {
        LinkedNode* cur = dummyhead;
        LinkedNode* newnode = new LinkedNode(val);
        while(size_){
            cur = cur->next;
            size_--;
        }
        cur->next = newnode;
        size_++;//添加了元素，链表大小加1
    }

如果想要使用这个量用于while循环的条件判定，可以将size_赋值给一个新变量n，代码如下，这时，代码就是正确的了

void addAtTail(int val) {
        int n = size_;
        LinkedNode* cur = dummyhead;
        LinkedNode* newnode = new LinkedNode(val);
        while(n){
            cur = cur->next;
            n--;
        }
        cur->next = newnode;
        size_++;//添加了元素，链表大小加1
    }

⑤在第n个节点处插入一个节点

注意“坑”? ? ? ?：即顺序??

在第n个节点处插入一个节点，因此一定要知道第n-1个节点，所以cur=dummyhead

代码

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;
            index--;
        }
        newnode->next = cur->next;
        cur->next = newnode;
        size_++;//新加入了节点，链表大小要加1
    }

⑥删除第n个节点

删除第n个节点，一定要知道第n-1个节点，因此，cur=dummyhead

代码

void deleteAtIndex(int index) {
        if(index>(size_-1)||index<0) return;
        LinkedNode* cur = dummyhead;
        while(index){
            cur = cur->next;
            index--;
        }
        //注意释放内存
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        size_--;//删除了一个元素，链表大小减1
    }

整体代码

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<0 || index>(size_-1)) return -1;
        LinkedNode* cur = dummyhead;
        while(index){
            cur = cur->next;
            index--;
        }
        return cur->next->val;   
    }
    void addAtHead(int val) {
        LinkedNode* newnode = new LinkedNode(val);
        newnode->next = dummyhead->next;
        dummyhead->next = newnode;
        size_ ++;//注意添加了元素，要在原链表的基础上加1
    }
    void addAtTail(int val) {
        LinkedNode* cur = dummyhead;
        LinkedNode* newnode = new LinkedNode(val);
        while(cur->next!=nullptr){
            cur = cur->next;

        }
        cur->next = newnode;
        size_++;//添加了元素，链表大小加1
    }
    
    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;
            index--;
        }
        newnode->next = cur->next;
        cur->next = newnode;
        size_++;//新加入了节点，链表大小要加1
    }

    void deleteAtIndex(int index) {
        if(index>(size_-1)||index<0) return;
        LinkedNode* cur = dummyhead;
        while(index){
            cur = cur->next;
            index--;
        }
        //注意释放内存
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        size_--;//删除了一个元素，链表大小减1
    }
    void printLinkedList() {
        LinkedNode* cur = dummyhead;
        while(cur->next!=nullptr){
            cout<<cur->next->val<<" ";
            cur = cur->next;
        }
        cout<<endl;  
    }
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);
 */
 // 打印链表

时间复杂度: 涉及?index?的相关操作为 O(index), 其余为 O(1)
空间复杂度: O(n)? 其中 n?为链表的长度。需要为每个节点分配内存空间来存储节点的值和下一个节点的指针，并且还需要一个额外的虚拟头节点指向链表的头部。

题目3：206 反转链表（面试高频）

题目链接：206 反转链表

题意

根据链表的头节点head? 返回反转后的链表

双指针

代码

/**
 * 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) {
       ListNode* pre = NULL;
       ListNode* cur = head;
       while(cur!=NULL){
           ListNode* temp = cur->next;
           cur->next = pre;
           //pre，cur向后移动一位
           pre = cur;
           cur = temp;
       }
       return pre;
    }
};

时间复杂度: O(n)
空间复杂度: O(1)

递归

代码

/**
 * 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* reverse(ListNode* cur, ListNode* pre){
        //终止条件
        if(cur==NULL) return pre;
        //单层递归逻辑
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(temp,cur);
    }
    ListNode* reverseList(ListNode* head) {
       return reverse(head,NULL);
    }
};

时间复杂度: O(n), 要递归处理链表的每个节点
空间复杂度: O(n), 递归调用了 n 层栈空间

文章来源:https://blog.csdn.net/qq_43773652/article/details/135352082
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！

day03 移除链表元素 设计链表 反转链表

题目1：203 移除链表元素

题目链接：203 移除链表

题意

分类讨论

虚拟头节点

题目2：707 设计链表

题目链接：707 设计链表

题意

①初始化节点

②获取链表的某个节点值? （index从0开始，head的index为0）

法1：cur指向dummyhead

法2：cur指向dummyhead->next

③在头节点前面插入一个节点

④在尾节点后面插入一个节点

⑤在第n个节点处插入一个节点

⑥删除第n个节点

题目3：206 反转链表（面试高频）

题目链接：206 反转链表

题意

双指针

递归

day03 移除链表元素设计链表反转链表