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

输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f

来源：力扣（LeetCode）
*/

/*
说明：
不知道该节点前驱，因此无法直接删除该节点；
可以用该节点取代它的下一个节点，然后把它的下一个节点删掉；
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
	struct ListNode* tmpNode = node->next;
	
    node->val = node->next->val;
	node->next = node->next->next;
	tmpNode->next = NULL;
	free(tmpNode);
}

删除链表的中间节点
删除链表的中间节点
public static LinkNode removeHalfNode(LinkNode node) {
		if(node==null || node.next==null) {
			return node;
		}
		if (node.next.next==null) {
			return node.next;
		}
		LinkNode fast = node.next.next;
		LinkNode slow = node; //重点slow指的是要删除节点的前一个节点
		while(fast!=null&&fast.next!=null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		slow.next= slow.next.next;
		return node;
	}

转自：http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-delete.html

 

 

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.java
						
To run:          java testProg2
					
				
 

		
The Heap class Prog file: click here
			
The test Prog file: click here
		
	
	
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))       
					
				
	

项目场景：
实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。
示例：
输入：单向链表a->b->c->d->e->f中的节点c

结果：不返回任何数据，但该链表变为a->b->d->e->f
问题描述：
free(node->next);

加这句将出现AddressSanitizer: heap-use-after-free报错，不加将存在一个无用节点node->next浪费内存（但好像无法解决）
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //由于只能访问该节点
void deleteNode(struct ListNode* node)
{
    node->val = node->next->val;
    node->next = node->next->next;
    //free(node->next);
}

 

原因分析：
释放node->next内存将对前面对此节点内容的使用造成内存访问上的错误：

Use after free：访问堆上已经被释放的内存

Heap buffer overflow：堆上缓冲区访问溢出

Stack buffer overflow：栈上缓冲区访问溢出

Global buffer overflow：全局缓冲区访问溢出

Use after return：访问栈上已被释放的内存

Use after scope：栈对象使用超过定义范围

Initialization order bugs：初始化命令错误

Memory leaks：内存泄漏
解决方案：
注释掉free那句即可
【附AddressSanitizer常见报错】

应用 AddressSanitizer 发现程序内存错误

【附其他人解法：添加临时变量】

（我不觉得有什么区别，但大家好像都用临时变量）
void deleteNode(struct ListNode* node) {
    struct ListNode* temp = node->next;
    node->val = node->next->val;
    node->next = node->next->next;
    free(temp);
}