203移除链表元素&707设计链表&206反转链表

day3

203.移除链表元素

链表的基本知识（注意C++中如何构造链表）：

//单链表
struct ListNode{
    int val; //节点上存储的元素
    ListNode* next;	//指向下一个节点的指针
    ListNode(int x): val(x), next(NULL) {}	//节点的构造函数
}
同时注意自己建立构造函数和默认构造函数的区别（如下图）。

解题思路：两种方法

第一种：直接在原来链表进行操作，分两种情况，一种是删除头节点一种是删除中间节点，注意在C++中需要手动释放节点内存。

第二种：使用虚拟头节点，将虚拟头节点指向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;

        //使用虚拟头节点解决
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while( cur->next != NULL ){
            if ( cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else{
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
        // return dummyHead->next;
}
};

707.设计链表

题目链接：707.设计链表

解决思路：还是采用虚拟头节点的方式

1.获取第n个节点的值，定义虚拟头节点dummyhead,注意第n个节点的n代表的是下标，如果不能理解可以举例一种极端的情况；先判断index是否有效。

2.头部插入节点定义一个新的节点，先将新节点指向头部节点指针，然后再将虚拟节点指向定义的新节点
newnode->next = dummyhead->next;
dummyhead->next = newnode;
//注意这里先后顺序
3.尾部插入节点，先定义一个新节点，然后遍历链表当链表的下一个指向值为NULL时，令
cur->next = newnode;
4.第n个节点前插入节点，先对题目描述的几种情况进行处理，最后对节点进行插入
newnode->next = cur -> next;
cur -> next = newnode;
//注意先后顺序问题，
5.删除第index个节点，第n个节点是cur->next
cur->next = cur->next->next;

总结：对于插入和删除的操作，核心在于更新cur->next节点。

// 注意C++中对于单向链表的定义。
class MyLinkedList {
public:
    //定义链表节点结构体
    struct LinkedNode{
        int val;
        LinkedNode* next;
        LinkedNode(int val): val(val), next(nullptr){}
    };
    // 初始化链表
    MyLinkedList() {
        dummyHead = new LinkedNode(0);//定义虚拟头节点
        size = 0;

    }
    // 获取链表中第index节点的值
    int get(int index) {
        if( index > (size - 1) || index < 0){
            return -1;
        }

        LinkedNode* cur = dummyHead->next;
        while( index-- ){
            cur = cur->next;
        }
        return cur->val;

    }
    // 在链表的第一个元素之前添加值val
    void addAtHead(int val) {
        LinkedNode* newnode = new LinkedNode(val);
        newnode->next = dummyHead->next;
        dummyHead->next = newnode;
        size++;

    }
    //在链表的结尾追加一个值为val的节点
    void addAtTail(int val) {
        LinkedNode* newnode = new LinkedNode(val);
        // newnode->val = val;
        LinkedNode* cur = dummyHead;
        while( cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newnode;
        size++;
    }
    //在链表中的第index位置添加值为val的节点
    // 1.如果index>size 返回空
    // 2.如果index=size 在尾部插入节点
    // 3.如果index<0 在头部插入节点
    // 4.剩下情况在中间插入节点
    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;
        }
        newnode->next = cur->next;
        cur->next = newnode;
        size++;

    }
    //删除第index个节点
    void deleteAtIndex(int index) {
        if( index >= size || index < 0){
            return;
        }
        LinkedNode* cur = dummyHead;
        while ( index-- ){
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }
    // 打印链表
    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);
 */

206.反转链表

题目链接：206.反转链表

解题思路：双指针法和递归法

1.双指针法：定义两个指针一个指向NULL，一个指向head
pre = NULL;
cur = head;
// 转换指针指向 注意得提前将cur->next存到临时变量里面
cur->next = 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* reverse( ListNode* pre,ListNode* cur){
        if( cur == NULL) return pre;
        ListNode* tmp = cur->next;
        cur->next = pre;
        // 可以和双指针发进行比较
        // pre = cur;
        // cur = tmp;
        return reverse( cur,tmp );
    }
    ListNode* reverseList(ListNode* head) {
        // // 双指针法
        // ListNode* cur = head;
        // ListNode* pre = nullptr;
        // while( cur ){
        //     //先存着cur的下一个变量
        //     ListNode* tmp = cur -> next;
        //     // 更改链表的方向
        //     cur->next = pre;
        //     //双指针往前走
        //     pre = cur;
        //     cur = tmp;
        //     // delete tmp;

        // }
        // // delete tmp;
        // // 最终新链表的head为pre。
        // return pre;

        // 递归法
        // 和双指针方法是一样的
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse( NULL,head );


    }
};

上篇977有序数组的平方&209长度最小的子数组&59螺旋矩阵II

下篇142环形链表II&面试题02.07链表相交&19删除链表的倒数第N个节点&24两两交换链表中的节点