• 删除堆的中间节点
2022-01-06 18:08:27

这可能是个面试题

若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。

假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。

例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

public void deleteNode(ListNode node) {
node.val=node.next.val;
node.next=node.next.next;

}

更多相关内容
• ## 图解-堆删除节点

千次阅读 2018-12-04 18:06:34
转自：http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-delete.html     Deleting a specific node from a Heap     ... You are given a heap...

• Deleting a specific node from a Heap

• Problem description:

• You are given a heap.

For example:

• You are also given a index k

For example: k = 2

• Problem:

 Delete the value a[k] from the heap (so that the resulting tree is also a heap !!!)

• Here is a Heap with the element a[2] = 5 deleted:

Heap before deleting the value a[2] = 5
Heap after the deletion...

\$64,000 question:

 How did you do it ???

• The delete algorithm for a Heap

• The heap deletion algorithm in pseudo code:

  1, Delete a node from the array (this creates a "hole" and the tree is no longer "complete") 2. Replace the deletion node with the "fartest right node" on the lowest level of the Binary Tree (This step makes the tree into a "complete binary tree") 3. Heapify (fix the heap): if ( value in replacement node < its parent node ) Filter the replacement node UP the binary tree else Filter the replacement node DOWN the binary tree 

• Example:

• Delete the node containing the value 5 from the following heap:

After you delete the node, the tree is not a complete binary tree:

• Step 1: replace the deleted node with the node in the "fartest right location" of the lowest level

Result:

However, it is not a heap:

• We must fix the binary tree so that it becomes a heap again !!!

 Depending on the value of the replacement node, we must filter the replacement node upwards ordownwards

Since you have already seen the filter up algorithm --- in the heap insert algorithm --- I made the example to show you the filter down algorithm now

• Step 2: because the replacement node 21 is greater than its parent node (1), we must filter the replacement node down the tree

Filter the replacement node down the tree proceeds as follows:

• Compare the values of the replacement node with all its children nodes in the tree:

Some child node has a smaller value: the replacement node is not in its proper location

• Swap the replacement node with the smallest of the children nodes:

• After swapping:

Repeat !

• Compare the values of the replacement node (21) with all its children nodes in the tree:

Some child node has a smaller value: the replacement node is not in its proper location

• Swap the replacement node with the smallest of the children nodes:

After swapping:

Repeat !

• The replacement node (21) does not have any children node:

Done !!!

• Warning:

 Sometimes, you have to filter the replacement node up the Binary tree !!!!!

Example:

• Delete the node with value = 33 from the following heap:

• Step 1: replace the deleted node with the "last" node in the lowest level (to make a complete binary tree)

Result:

• In this case, the replacement node must be filtered up into the binary tree:

Result:

• Conclusion:

  if ( replacement node < its parent node ) filter the replacement node up the tree else filter the replacement node down the tree 

• Heap deletion algorithm in Java:

  public double remove( int k ) { int parent; double r; // Variable to hold deleted value r = a[k]; // Save return value a[k] = a[NNodes]; // Replace deleted node with the right most leaf // This fixes the "complete bin. tree" property NNodes--; // One less node in heap.... parent = k/2; /* ======================================================= Filter a[k] up or down depending on the result of: a[k] <==> a[k's parent] ======================================================= */ if ( k == 1 /* k is root */ || a[parent] < a[k] ) HeapFilterDown(k); // Move the node a[k] DOWN the tree else HeapFilterUp(k); // Move the node a[k] UP the tree return r; // Return deleted value... } 

(We have already discussed the HeapFilterUp() algorithm .... )

• Filter Down algorithm in pseudo code:

  HeapFilterDown( k ) // Filter node a[k] down to its proper place { while ( a[k] has at least 1 child node ) { child1 = 2*k; // left child of a[k] child2 = 2*k + 1; // right child of a[k] if ( a[k] has 2 childred nodes ) { if ( a[k] has smallest value among {a[k], a[child1], a[child2]} ) break; // a[k] in proper place, done else { /* ========================================= Replace a[k] with the smaller child node ========================================= */ if ( a[child1] < a[child2] ) { swap ( a[k], a[child1] ); k = child1; // Continue check.... } else { swap ( a[k], a[child2] ); k = child2; // Continue check... } } } else // a[k] must have only 1 child node { if ( a[k] has smallest value among {a[k], a[child1]} ) break; // a[k] in proper place, done else { swap ( a[k], a[child1] ); k = child1; // Continue check.... } } } 

• The Filter down algorithm (describe above) is coded as a method:

  /* ======================================================== HeapFilterDown(k): Filters the node a[k] down the heap ======================================================== */ void HeapFilterDown( int k ) { int child1, child2; // Indices of the children nodes of k double help; while ( 2*k <= NNodes ) // Does k have any child node ? { child1 = 2*k; // Child1 = left child of k child2 = 2*k+1; // Child2 = right child of k if ( child2 <= NNodes ) // If true, then k has 2 children nodes ! { /* ======================================== Node k has 2 children nodes.... Find the min. of 3 nodes !!! ======================================== */ if ( a[k] < a[child1] && a[k] < a[child2] ) { /* ------------------------------------------------------- Node k has the smallest value ! Node k is in correct location... It's a heap. Stop... ------------------------------------------------------- */ break; // STOP, it's a heap now } else { /* =================================================== Swap a[k] with the smaller of its 2 children nodes =================================================== */ if ( a[child1] < a[child2] ) { /* ------------------------------------------------------- Child1 is smaller: swap a[k] with a[child1] ------------------------------------------------------- */ help = a[k]; a[k] = a[child1]; a[child1] = help; k = child1; // Replacement node is a[child1] // in next iteration } else { /* ------------------------------------------------------- Child2 is smaller: swap a[k] with a[child2] ------------------------------------------------------- */ help = a[k]; a[k] = a[child2]; a[child2] = help; k = child2; // Replacement node is a[child2] // in next iteration } } } else { /* ======================================== Node k only has a left child node Find the min. of 2 nodes !!! ======================================== */ if ( a[k] < a[child1] ) { /* ------------------------------------------------------- Node k is in correct location... It's a heap. Stop... ------------------------------------------------------- */ break; } else { /* ------------------------------------------------------- Child1 is smaller: swap a[k] with a[child1] ------------------------------------------------------- */ help = a[k]; a[k] = a[child1]; a[child1] = help; k = child1; // Replacement node is a[child1] // in next iteration } } } } 

• Example Program: (Demo above code)

How to run the program:

 Right click on link and save in a scratch directory   To compile:   javac testProg2.javaTo run:          java testProg2

• Running time analysis of the heap delete algorithm

• Before we can perform a running time analysis, we must first understand how the algorithm works exactly...

• Summary of the heap delete algorithm:

• The deleted node is first replaced:

We will always have a complete binary tree:

• Then the HeapFilterUp() or the HeapFilterDown() algorithm will migrate the replacement node up or down into the binary tree:

and:

• Fact:

• The number of times that the deleted node will migrate up or down into the binary tree is:

  # migrations ≤ height of the binary tree 

Example:

• The maximum number of times that replacement node can move down in a binary tree:

is at most 3 times:

The same argument can be apply to show that the maximum number of times that a nodes can move up the tree is at most the height of the tree.

• Therefore:

  Running time( delete(n) ) = Running time heap delete in heap with n node = height of a heap of n nodes 

• The height of a heap when it contains n nodes

• We have already determined this fact:

  Let: n = # nodes in heap of height h 2h - 1 < n ≤ 2h+1 − 1 <===> 2h < n + 1 ≤ 2h+1 <===> h < lg(n + 1) ≤ h+1 ===> height of heap ~= lg(n + 1) 

• Running time of the heap delete algorithm

• Summary:

 Running time of delete into a heap of n nodes = height of the heap     height of the heap containing n nodes ~= lg(n + 1)

• Conclusion:

 Running time of delete into a heap of n nodes = O(lg(n))
展开全文
• 思路：把我变成你然后再删掉你就相当于删掉了我自己 /* *public class ListNode { * int value; * ListNode next; * ListNode(int x) { val = x; } * } */ class Main{ public void deleteNode(ListNode node){ ...

思路：把我变成你然后再删掉你就相当于删掉了我自己

/*
*public class ListNode {
*     int value;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Main{
public void deleteNode(ListNode node){
node.value = node.next.value;
node.next = node.next.next;
}
}


展开全文
• 删除中间节点 问题： 实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。 思路： 例：a->b->c->d->e->f 删除节点 b； 只知道 b 的地址，所以采用...

## 删除中间节点

问题：
实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

思路：
例：a->b->c->d->e->f
删除节点 b；
只知道 b 的地址，所以采用后一结点覆盖之的方法来解决这个问题
让 b 的数据变为 c，b 的指针指向 d 即可

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};

展开全文
• 实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。 示例： 输入：单向链表a->b->c->d->e->f中的节点c 结果：不返回任何数据，但该链表变为a->b-&...
• 常用节点解读】：一、将UV坐标系变成笛卡尔直角坐标系(锚点由左上角变换到中心)二、圆形遮罩三、线性遮罩四、旋转图片五、植被地形六、后处理七、UI播放视频八、常用函数算法九、做多边形十、做特效十一、If提取图片...
• 定义：n个关键字序列称为，当且仅当该序列满足下列两个条件中的一个： L(i)⩽L(2i)且L(i)⩽L(2i+1)L(i)\leqslant L(2i)且L(i)\leqslant L(2i+1)L(i)⩽L(2i)且L(i)⩽L(2i+1) ① 小根 L(i)⩾L(2i)且L(i)⩾L(2i+1...
• 不算是一种数据结构,只是一类数据结构的统称,通常用完全二叉树来实现.完全二叉树即除了叶子节点外,必须存在左右孩子节点的树.不完全二叉树是除了叶子节点外,存在一个或多个节不完全存在左右孩子节点.在前面小编...
• 2.删除 3.的插入 三、完整源码与小结 1.完整源码 2.小结 一、的介绍 如果有一个关键码的集合K={k0,k1,k2,k3,......k(n-1)},把所有的元素按照完全二叉树的顺序存储方式存储在一个一维数组中，并满足...
• 实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。 示例： 输入：单向链表a->b->c->d->e->f中的节点c 结果：不返回任何数据，但该链表变为a->b-&...
•  1、定义一个中间变量来暂时寄存要删除节点后面的链表元素  2、删除节点(free()函数)  3、将剩余的节点与重新关联起来   删除中间某一个值的节点：  1、遍历链表，找到要删除节点的位置  2、定义一个...
• 看到这个题我先想到的是之前做过链表面试题中的：查找链表的倒数第K个节点（要求只遍历一次链表），而删除的话就是另外一个面试题：删除链表的pos节点；另外一种就是在OJ下实现的方法。 相关的链表面试题： C语言...
• 为什么说排序没有快速排序快？如何理解“”？... 删除堆顶元素；如何基于实现排序？的应用一：优先级队列；的应用二：利用求 Top K；的应用三：利用求中位数；一篇博客带你深入理解（Heap）
• 在最大构造,排序,和最大维护的基础上,补充了的插入和删除,和其中用到的上浮,下沉等操作。 个人理解：最大维护是用元素A替换掉中某元素后通过最大维护操作使得该依然是最大. 而插入则是插入元素A后...
• 其中，我们把根节点最大的叫做大顶堆，根节点最小的叫做小顶堆。 2.详解 2.1满二叉树 满二叉树是指所有层都达到最大节点数的二叉树。比如，下面这颗树： 2.2完全二叉树 完全二叉树是指除了最后一层其它...
• 的定义：是一种经过排序的完全二叉树或满二叉树， 最大：就是不不断变得进行树元素替换，最终是树呈现上面数值最大； 最小：就是不不断变得进行树元素替换，最终是树呈现上面数值最小；   的定义 ...
• ## 堆

2021-01-23 20:29:21
最小节点的值是中最小的，以最小为例子，如下图 他是数组结构，结点中的数字是数组元素的下标，不是数组元素的值。所以如果我们知道父节点的下标我们就可以知道他的两个子节点（如果有子节点），如果知道子...
• 文章目录一、二叉二、相关操作2.1 插入节点2.2 删除节点2.3 构建二叉三、优先队列四、排序五、其余补充 学习自书籍——《小灰的算法之旅》~ 一、二叉 二叉本质上是一种完全二叉树，分为大根和小根...
• ## 堆排序算法详解

万次阅读 多人点赞 2018-10-14 16:45:41
此时，整个序列的最大值就是顶的根节点。将它移走(其实就是将其与数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个，这样就会得到n个元素中的次最大值。如此反复执行，就能...
• 优先队列的二叉实现 在前面的章节里我们学习了“先进先出”（FIFO）的数据结构：队列（Queue）。队列有一种变体叫做“优先队列”（Priority Queue）。优先队列的出队（Dequeue）操作和队列一样，都是从队首出队。...
• ## 堆（大根堆、小根堆）

万次阅读 多人点赞 2020-05-26 20:51:02
本文介绍完全二叉，包括大根、小根。相关的算法(大根、小根)的插入、删除、批量建立。
• 1.节点的度与树的度 节点的度：结点拥有的子树数目称为结点的度，叶子结点 就是度为0的结点 树的度：树内各结点的度的最大值 分支节点：度不为0的节点 -------------------------------------------------- ...
• ## 堆排序【手写小根堆】

多人点赞 热门讨论 2022-06-25 12:23:38
排序,小根,大根,完全二叉树,向下调整,向上调整,down,up 是一个高效的优先级队列，我们可以把看做一棵完全二叉树的...在的创建过程中，我们需要加入两个操作：为什么是从最后一个非叶子节点开始down呢？...
• 1、创建一个结构体：创建一个包含自身结构的结构体，该结构体包含一个数据...3、初始化创建链表：创建链表要分为头插法和尾插法，该部分要注意用malloc申请的空间是在里面，而用int等定义的申请的空间是在栈里面。 3
• 这种数据结构的应用场景非常多，最经典的莫过于排序了。排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。我们知道，快速排序在平均情况下的时间复杂度为O(nlogn)。尽管这两种排序算法的时间复杂度都是 O...
• leetcode正方体收藏Striver - SDE 的重要问题 这些问题完全基于面试。 第一天：（数组） 在 N+1 整数数组中查找重复项。...在不使用额外空间或排序算法的情况下对 ...的中间 ...后面删除第 ...给定节点删除给定节点
• 关于原生JS获取节点，一直是个头疼的问题，而且调用方法的名字又贼长了，所以我选择用JQ，好像跑题了--话不多说看代码获取父节点 及 父节点下所有子节点(兄弟节点)文本一文本二文本三文本四function jsCopy(ev){var ...
• 目 录： 一、的基本概念 二、的实现 1  往中插入一个元素 ... 2、中的一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。 回顾：完全二叉树：除了最后一层，其他层的节.

...