LeetCode算法解题集:Delete Node in a Linked List

题目：
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

思路：
刚开始没怎么看懂题目，明明是删除一个节点需要的输入参数是链表和节点，但题目给出参数只有节点，后来查了资料，才明白有一种思路叫做“狸猫换太子”，输入一个节点，把这个节点的下一个值赋值到这个节点，并删除下一个节点就OK了，而不是找到上一个节点的指向。算法复杂度：O(1)

代码：

/**

• 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) {
    if( node == NULL || node->next == NULL )
    {
        return;
    }
     
    ListNode *pNextNode = node->next;
    node->val = pNextNode->val;
    node->next = pNextNode->next;
    delete pNextNode;
}

};