代码随想录算法训练营第2天 | 203.移除链表元素、707. 设计链表、206.反转链表203.移除链表元素题目描述解题思路解题过程707. 设计链表题目描述解题思路解题过程206.反转链表题目描述解题思路解题过程203.移除链表元素题目链接203.移除链表元素题目描述解题思路单链表删除结点的操作可以分为两种情况一种是删除头结点一种是其他结点。若要删头结点需要先使用一个临时结点将头结点改变成下一个结点再释放。非头结点就只需要遍历链表找到需要删除的结点进行删除即可。另一种设置虚拟头结点的方式就可以不用判断是否是头结点还是非头结点。删除链表的操作是将前一个结点的指针指向第二个结点。解题过程// 一般删除办法/** * 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) {} * }; */classSolution{public:ListNode*removeElements(ListNode*head,intval){while(head!nullptrhead-valval){ListNode*tmphead;headhead-next;deletetmp;}ListNode*curhead;while(cur!nullptrcur-next!NULL){if(cur-next-valval){ListNode*tmpcur-next;cur-nextcur-next-next;deletetmp;}elsecurcur-next;}returnhead;}};// 虚拟头结点classSolution{public:ListNode*removeElements(ListNode*head,intval){ListNode*dumynewListNode(0);dumy-nexthead;ListNode*curdumy;while(cur-next!nullptr){if(cur-next-valval){ListNode*tmpcur-next;cur-nextcur-next-next;deletetmp;}elsecurcur-next;}headdumy-next;deletedumy;returnhead;}};707. 设计链表题目链接707. 设计链表题目描述解题思路对于链表的完整构建与操作。解题过程classMyLinkedList{public:structListNode{intval;ListNode*next;ListNode(intval):val(val),next(nullptr){}};MyLinkedList(){_dumynewListNode(0);_size0;}intget(intindex){if(index(_size-1)||index0)return-1;ListNode*cur_dumy-next;while(index--){curcur-next;}returncur-val;}voidaddAtHead(intval){ListNode*newNodenewListNode(val);newNode-next_dumy-next;_dumy-nextnewNode;_size;}voidaddAtTail(intval){ListNode*newNodenewListNode(val);ListNode*cur_dumy;while(cur-next!nullptr){curcur-next;}cur-nextnewNode;_size;}voidaddAtIndex(intindex,intval){if(index_size)return;if(index0)index0;ListNode*newNodenewListNode(val);ListNode*cur_dumy;while(index--){curcur-next;}newNode-nextcur-next;cur-nextnewNode;_size;}voiddeleteAtIndex(intindex){if(index_size||index0)return;ListNode*cur_dumy;while(index--){curcur-next;}ListNode*tmpcur-next;cur-nextcur-next-next;deletetmp;tmpnullptr;_size--;}private:ListNode*_dumy;int_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.反转链表题目链接206.反转链表题目描述解题思路首先定义一个cur指针指向头结点再定义一个pre指针初始化为null。然后就开始反转首先要把 cur-next 节点用tmp指针保存一下也就是保存一下这个节点然后将cur - next 指向pre再移动pre和cur指针向前移动。当cur指向空到达结束点。解题过程/** * 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) {} * }; */classSolution{public:ListNode*reverseList(ListNode*head){ListNode*temp;ListNode*curhead;ListNode*preNULL;while(cur){tempcur-next;cur-nextpre;precur;curtemp;}returnpre;}};