参考文章均来自代码随想录LeetCode 203 移除链表元素参考文章链接题意删除链表中等于给定值 val 的所有节点。示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 示例 2 输入head [], val 1 输出[] 示例 3 输入head [7,7,7,7], val 7 输出[]正常可采用原链表删除即可优化是使用虚拟头结点 这样就不用单独处理删除头结点 逻辑更清楚// 虚拟头结点删除classSolution{public:ListNode*removeElements(ListNode*head,intval){ListNode*dummyHeadListNode(0);dummyHead-nexthead;// 设置一个虚拟头结点并指向头结点 方便删除操作ListNode*curdummyHead;while(cur-next!NULL){if(cur-next-valval){ListNode*tmpcur-next;cur-nextcur-next-next;deletetmp;}else{curcur-next;}}headdummyHead-next;deletedummyHead;returnhead;}};时间复杂度O(n)空间复杂度O(1)递归方法还需要进一步理解 比较不好想classSolution{public:ListNode*removeElements(ListNode*head,intval){// 基础情况空链表if(headnullptr){returnnullptr;}// 递归处理if(head-valval){ListNode*newHeadremoveElements(head-next,val);deletehead;returnnewHead;}else{head-nextremoveElements(head-next,val);returnhead;}}};LeetCode 707 设计链表参考文章链接示例 输入 [MyLinkedList, addAtHead, addAtTail, addAtIndex, get, deleteAtIndex, get] [[], [1], [3], [1, 2], [1], [1], [1]] 输出 [null, null, null, null, 2, null, 3] 解释 MyLinkedList myLinkedList new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1-2-3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在链表变为 1-3 myLinkedList.get(1); // 返回 3主要考察实现链表的操作 继续熟练虚拟头结点classMyLinkedList{public:structLinkNode{intval;LinkNode*next;LinkNode(intval):val(val),next(nullptr){}};//初始化MyLinkedList(){_dummyHeadnewLinkNode(0);_size0;}intget(intindex){if(index(_size-1)||index0)return-1;LinkNode*cur_dummyHead-next;while(index--){curcur-next;}returncur-val;}voidaddAtHead(intval){LinkNode*newNodenewLinkNode(val);newNode-next_dummyHead-next;_dummyHead-nextnewNode;_size;}voidaddAtTail(intval){LinkNode*newNodenewLinkNode(val);LinkNode*cur_dummyHead;while(cur-next!nullptr){curcur-next;}cur-nextnewNode;_size;}voidaddAtIndex(intindex,intval){if(index_size)return;if(index0)index0;LinkNode*newNodenewLinkNode(val);LinkNode*cur_dummyHead;while(index--){curcur-next;}newNode-nextcur-next;cur-nextnewNode;_size;}voiddeleteAtIndex(intindex){if(index_size||index0)return;LinkNode*cur_dummyHead;while(index--){curcur-next;}LinkNode*tmpcur-next;cur-nextcur-next-next;deletetmp;tmpnullptr;_size--;}voidprint(){LinkNode*cur_dummyHead;while(cur-nextnullptr){coutcur-next-val ;curcur-next;}coutendl;}private:int_size;LinkNode*_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); */时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)空间复杂度: O(n)LeetCode 206 反转链表参考文章链接题意反转一个单链表。示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL双指针法进行反转classSolution{public:ListNode*reverseList(ListNode*head){ListNode*temp;// 保存cur的下一个节点ListNode*curhead;ListNode*preNULL;while(cur){tempcur-next;cur-nextpre;// 翻转// 更新precur;curtemp;}returnpre;}};时间复杂度: O(n)空间复杂度: O(1)还可以递归法解决 对此处理解还不够深 多看参考文章的代码进行理解