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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。