北京网页设计公司兴田德润怎么样,泰州网站排名seo,域名是企业的网上商标,微信公众号的字体和wordpress若链表中的某个节点#xff0c;既不是链表头节点#xff0c;也不是链表尾节点#xff0c;则称其为该链表的「中间节点」。
假定已知链表的某一个中间节点#xff0c;请实现一种算法#xff0c;将该节点从链表中删除。
例如#xff0c;传入节点 c#xff08;位于单向链…若链表中的某个节点既不是链表头节点也不是链表尾节点则称其为该链表的「中间节点」。
假定已知链表的某一个中间节点请实现一种算法将该节点从链表中删除。
例如传入节点 c位于单向链表 a-b-c-d-e-f 中将其删除后剩余链表为 a-b-d-e-f
示例
输入节点 5 位于单向链表 4-5-1-9 中
输出不返回任何数据从链表中删除传入的节点 5使链表变为 4-1-9
这道题的方法很简单只要清楚链表的储存方式就可以。已知给出的中间节点为node那么我们想要删除这个节点只需要将这个节点的值变为下一个节点的值我们就得到了两个值相同的节点然后我们将下下个节点指向需要删除节点的下一个节点就完成删除了。实际上是删除了中间节点的下一个节点但是因为我们因为将下一个节点的值赋给中间节点因此我们可以直接删除中间节点的下一个节点。这样说可能不太清楚其实我们把我们要删除的节点定义为当前节点那么我们就可以直接让当前节点的前驱节点指向后继节点就实现了删除。类比到这个题里当前节点并不是题目中给出的中间节点而是它的下一个节点因此我们先将中间节点的值变为下一个节点的值再删除下一个节点那么实际看到的结果就是删除了中间节点。
leetcode代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:void deleteNode(ListNode* node) {node-valnode-next-val;node-nextnode-next-next;}
};
其实我一开始没有注意到这个题是直接给出要删除的节点我以为的中间节点是要自己找的。理解错题意了。那么如果要找真正意义上的中间节点该怎么做呢请往下看
其实找中间节点主要是看数的总数为偶数的情况到底是选择靠前的那个节点还是靠后的节点而思路和上一个找倒数第k个节点的题类似都是使用双指针去找同样将两个指针先指向头节点而中间节点就是在1/2的位置那么我们只要让两个指针的移动速度为两倍差但是如果数的个数为偶数的话那么找到的节点就是靠后的那个节点。
leetcode代码
class Solution {
public:ListNode* middleNode(ListNode* head) {if(headnullptrhead-nextnullptr){return head;}ListNode *p head;ListNode *q head;while(p ! nullptr q-next ! nullptr) {q q-next;p p-next-next;}return q;}
};
那么如果我们要找到的是靠前的那个节点呢
class Solution {
public: ListNode* middleNode(ListNode* head) { if (head nullptr || head-next nullptr) { // 如果链表为空或只有一个节点则直接返回头节点 return head; } ListNode *p head; ListNode *q head; while (p-next ! nullptr p-next-next ! nullptr) { // p 每次移动两步直到 p-next 或 p-next-next 为空 p p-next-next; // q 每次移动一步 q q-next; } // 当 p 无法再安全地前进两步时即 p-next 或 p-next-next 为空q 指向“靠前的”中间节点 return q; }
};
