18_delete_node_in_list.md

删除链表中的结点

给定单链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。

这道题需要一点技巧，当只知道删除的结点，而不知道其前驱结点时，我们可以这样做：
将该结点的后面一个结点的值拷贝过来，然后将该结点的后一个结点给删除。

其他需要重点考虑的问题是：

1. 删除结点就是尾结点
2. 删除结点后面还有结点
3. 删除结点就是头结点

#include <iostream>

using namespace std;

#define NELEM(arr) (sizeof(arr)/sizeof(arr[0]))

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int v) : val(v), next(NULL) { }
};

class Solution {
public:
    void delete_node(ListNode **head, ListNode *to_delete) {
        if (!head || !*head || !to_delete) {
            return;
        }

        // Suppose to_delete is in the list, otherwise we need to check it with O(n).
        if (to_delete->next) {
            ListNode *next = to_delete->next;
            to_delete->val = next->val;
            to_delete->next = next->next;
            delete next;
        } else if (to_delete == *head) {
            // Delete the only one node in list.
            delete to_delete;
            *head = NULL;
        } else {
            // Delete the tail.
            ListNode *p = *head;
            while (p->next != to_delete) {
                p = p->next;
            }
            delete to_delete;
            p->next = NULL;
        }
    }
};

int create_list_by_array(const int arr[], const int n, ListNode *&head, ListNode *&tail)
{
    head = NULL;
    tail = NULL;

    if (!arr || n <= 0) {
        return -1;
    }

    for (int i = 0; i < n; i++) {
        ListNode *node = new ListNode(arr[i]);
        if (!head) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }

    return 0;
}

int destroy_list(ListNode *&head)
{
    ListNode *p, *q;
    p = head;
    while (p) {
        q = p->next;
        delete p;
        p = q;
    }
    head = NULL;

    return 0;
}

void print_list(ListNode *head)
{
    ListNode *p = head;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

int main(int argc, char const *argv[])
{
    int arr[] = { 1 };
    ListNode *head, *tail;
    create_list_by_array(arr, NELEM(arr), head, tail);
    Solution().delete_node(&head, head);
    print_list(head);
    destroy_list(head);

    int arr1[] = { 1, 2, 3, 4, 5 };
    create_list_by_array(arr1, NELEM(arr1), head, tail);
    ListNode *p = head->next->next->next;
    Solution().delete_node(&head, p);
    print_list(head);
    destroy_list(head);

    return 0;
}

输出结果：

1 2 3 5