代码随想录算法训练营第三天 | 203.移除链表元素 、 707.设计链表 、206.反转链表

203.移除链表元素

题目：. - 力扣（LeetCode）

思路：主要是通过运用虚拟头节点来统一移除元素的写法。

代码：

/**
 * 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* virhead=new ListNode(0,head);
    ListNode* cur=virhead;
    while(cur->next!=NULL){
        if(cur->next->val==val){
            ListNode* tem=cur->next;
            cur->next=cur->next->next;
            delete tem;
        }
        else
        cur=cur->next;
    }
    return virhead->next;
    }
};

707.设计链表

题目：. - 力扣（LeetCode）

思路：通调用增加结点函数来实现增加头节点和增加尾结点，难点是循环次数比较容易弄乱。

代码：

class MyLinkedList {
public:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode():val(0),next(NULL){};
        ListNode(int i):val(i),next(NULL){};
    };
    ListNode* virhead;
    int size;
    MyLinkedList() {
    virhead=new ListNode(0);
    size=0;
    }
    
    int get(int index) {
    if(index<0||index>size-1)
    return -1;
    ListNode* cur=virhead;
    for(int i=0;i<index+1;i++){
    cur=cur->next;
    }
    return cur->val;
    }
    
    void addAtHead(int val) {
    addAtIndex(0,val);
    }
    
    void addAtTail(int val) {
    addAtIndex(size,val);
    }
    
    void addAtIndex(int index, int val) {
    if(index<0||index>size)
    return;
    ListNode* cur=virhead;
    ListNode* tem=new ListNode(val);
    for(int i=0;i<index;i++){
        cur=cur->next;
    }
    tem->next=cur->next;
    cur->next=tem;
    size++;
    }
    
    void deleteAtIndex(int index) {
    if(index<0||index>size-1)
    return;
    ListNode* cur=virhead;
    for(int i=0;i<index;i++){
        cur=cur->next;
    }
    ListNode* tem=cur->next;
    cur->next=cur->next->next;
    delete tem;
    size--;
    }
};

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

206.反转链表

题目：. - 力扣（LeetCode）

思路：翻转的关键是每次要保存当前结点的前结点。

代码：

/**
 * 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* tem=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tem;
    }
    return pre;
    }
};