LeetCode算法解题集:Delete Node in a L

题目：
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;
    }
};

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-07-27