做网站应该了解什么,绵阳市做公司网站,合川网站制作,pc端网站怎么做自适应手机端题目1#xff1a;移除重复节点
编写代码#xff0c;移除未排序链表中的重复节点。保留最开始出现的节点。 输入#xff1a;[1, 2, 3, 3, 2, 1] 输出#xff1a;[1, 2, 3] 解题思路#xff1a; 1.创建一个set表#xff0c;将第一次出现的节点值保存起来 2.定义pre指针保…题目1移除重复节点
编写代码移除未排序链表中的重复节点。保留最开始出现的节点。 输入[1, 2, 3, 3, 2, 1] 输出[1, 2, 3] 解题思路 1.创建一个set表将第一次出现的节点值保存起来 2.定义pre指针保存前驱定义cur指针遍历链表 2.遍历链表如果当前节点是第一次出现那么就放入set表中pre的后继指向当前节点pre和cur都往后走 如果当前节点不是第一次出现那么pre不动cur往后走 源代码如下 class Solution {
public:ListNode* removeDuplicateNodes(ListNode* head) {if(headNULL) return head;unordered_setint visited(head-val);//定义一个set容器保存第一次出现的节点值ListNode* prehead;ListNode* curhead-next;while(cur){if(set.count(cur-val)0)//判断是否存在该节点{set.insert(cur-val);//插入元素pre-nextcur;prepre-next;}curcur-next;}//遍历完后cur此时应该指向nullptrpre-nextcur;//pre指针指向cur结束链表return head;}
};
题目2删除中间节点
若链表中的某个节点既不是链表头节点也不是链表尾节点则称其为该链表的「中间节点」。
假定已知链表的某一个中间节点请实现一种算法将该节点从链表中删除。
例如传入节点 c位于单向链表 a-b-c-d-e-f 中将其删除后剩余链表为 a-b-d-e-f 输入节点 5 位于单向链表 4-5-1-9 中
输出不返回任何数据从链表中删除传入的节点 5使链表变为 4-1-9解题思路
难点在于只知道中间节点的后继但不知道它的前驱节点 无法直接通过前驱指向后继实现本题。
所以我们可以将中间节点的后继节点值赋给中间节点那么此时链表变为了4-1-1-9 然后将中间节点的后继节点删除即可。
源代码如下
lass Solution {
public:void deleteNode(ListNode* node) {node-valnode-next-val;//把中间节点的后继节点的值赋给中间节点node-nextnode-next-next;//再将中间节点的后继节点删除即可}
};
