代码随想录算法训练营第三天

标签：head ListNode cur val 训练营 随想录 next 链表 算法

学习新知识链表，刷题3道，先学习链表理论基础，然后刷题。 203.移除链表元素 707.设计链表 206.反转链表

●  203.移除链表元素

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

碎碎念：思路都会，代码语法不知道怎么写，伪代码写的太多也不好，还是得上机啊，两个版本，第一个是不加虚拟头结点，第二个是加的，实践证明加了的好用。

ps:得补c++语法了，要学的可真多啊，我还在输液，心情很不美丽。

1.直接使用原来的链表来进行移除节点操作：

class Solution { public:     ListNode* removeElements(ListNode* head, int val) {         //删除头节点         while(head != NULL && head -> val == val){             ListNode* tmp = head;      //链表创建新指针             head = head -> next;             delete tmp;                //释放空间，c语言是free()         }         //删除非头结点。         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;     } };   2.设置一个虚拟头结点在进行移除节点操作： class Solution { public:     ListNode* removeElements(ListNode* head, int val) {         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;     } };

●  707.设计链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

 碎碎念：链表的常用操作，需要掌握。

class MyLinkedList { public:     struct LinkedNode{    //构建链表结点的结构体         int val;         LinkedNode* next;         LinkedNode(int val):val(val),next(nullptr){}     };     //初始化链表     MyLinkedList() {         dummyhead = new LinkedNode(0);    //定义虚拟头结点，不是真的结点         size = 0;     }     //获取链表中第 index 个节点的值。如果索引无效，则返回-1。     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);    //创建新结点，并赋值为val         newNode -> next = dummyhead -> next;         dummyhead -> next = newNode;         size++;     }     //将值为 val 的节点追加到链表的最后一个元素。     void addAtTail(int val) {         LinkedNode* newNode = new LinkedNode(val);         LinkedNode* cur = dummyhead;         while(cur -> next != nullptr){   //nullptr是C++空指针类型的关键字             cur = cur -> next;         }         cur -> next = newNode;         size++;     }     //在链表中的第 index 个节点之前添加值为 val  的节点。     //如果 index 等于链表的长度，则该节点将附加到链表的末尾。     //如果 index 大于链表长度，则不会插入节点。     //如果index小于0，则在头部插入节点。     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 有效，则删除链表中的第 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; };

 

●  206.反转链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

碎碎念：先是双链表指针法，然后根据它的思想可以改写成面试官偏爱的递归写法，emmmm，感觉遍历一遍，挨个头插也是可以的，回头试一下。

PS：休息了，不对，去打游戏了，好像有一点点心动的感觉，喜欢一个人就是要和她一起打很多很多把游戏，散会！

双链表指针法：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

递归法:

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }
};

　我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }
}; 

标签：head,ListNode,cur,val,训练营,随想录,next,链表,算法
From： https://www.cnblogs.com/zzw0612/p/17015133.html