您现在的位置是：首页 >其他 >代码随想录算法训练营第三天| 203.移除链表元素，707.设计链表，206.反转链表。网站首页其他

203.移除链表元素

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

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead=new ListNode();//设置虚拟头结点
        dummyHead->next=head;
        ListNode* cur=dummyHead;
        while(cur->next!=NULL){
            if(cur->next->val==val){//判断cur->next不为空才能使用这条
                ListNode* temp=cur->next;
                cur->next=cur->next->next;
                delete temp;
            }else{
                cur=cur->next;
            }
        }
        return dummyHead->next;
    } 
};

707.设计链表

1. 题目：你可以选择使用单链表或者双链表，设计并实现自己的链表。
   单链表中的节点应该具备两个属性：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 的节点
2. 题解：

class MyLinkedList {
//设计单链表
public:
    //定义节点结构体
    struct LinkNode{
        int val;
        LinkNode* next;
        //构造函数
        LinkNode(int val):val(val), next(nullptr){}
    };
    //定义变量
    LinkNode* dummyHead;
    int size;

    //初始化列表 构造函数
    MyLinkedList(){
        //虚拟头结点
        dummyHead=new LinkNode(0);
        //链表长度初始化为0
        size=0;
    }
    //获取链表中下标为index的节点的值
    int get(int index){
        //index满足规范
        if(index>=size||index<0) return -1;
        LinkNode* cur=dummyHead->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    void addAtHead(int val){
        LinkNode* newNode = new LinkNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }
    void addAtTail(int val){
        LinkNode* newNode = new LinkNode(val);
        LinkNode* cur = dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        size++;
    }
    void addAtIndex(int index,int val){
        if(index<0||index>size) return;
        LinkNode* addNode = new LinkNode(val);
        LinkNode* cur = dummyHead;
        while(index--){
            cur=cur->next;
        }
        addNode->next = cur->next;
        cur->next = addNode;
        size++;
    }
    void deleteAtIndex(int index){
        if(index<size&&index>=0){
            LinkNode* cur = dummyHead;
            while(index--){
                cur=cur->next;
            }
            LinkNode* temp=cur->next;
            cur->next=cur->next->next;
            delete temp;
            size--;
        }else{
            return;
        }
    }
};

206.反转链表

1. 题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
2. 题解：

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;
            cur=temp;
        }
        return pre;
    }
};