剑指offer(2)

发表于 | 分类于
本文总结剑指offer的编程题目，与使用C++实现的答案，快来挑战一下吧！

说明：本文题目答案分析来源《剑指offer》和牛客网，包含个人理解，仅为参考。强烈大家去阅读《剑指offer》原书。

fengjingtu

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

我们采用的方法是使用要删除节点的下一个几点覆盖它本身。如果是为节点则仍采用常规的遍历方式。

时间复杂度是()(n-1)*O(1)+O(n))/n,结果是O(1);

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>

using namespace std;
// 在o(1)时间删除链表节点

struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};
//这种方式并没有删除对应的指针指向的节点，而是改变了他的值。删除了他的下一个节点。
void DeleteNode(ListNode ** pListHead,ListNode *pToBeDeleted)
{
    if(pListHead==NULL || *pListHead ==NULL || pToBeDeleted ==NULL)
        return ;
    //如果删除的节点不是最后一个节点
    if(pToBeDeleted->m_pNext !=NULL )
    {
        ListNode * tmp= pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue=tmp->m_nValue;
        pToBeDeleted->m_pNext=tmp->m_pNext;
    }
    //如果删除的节点是尾节点也是头结点，链表中只有一个节点
    else if(pToBeDeleted->m_pNext ==NULL && *pListHead ==pToBeDeleted )
    {
        *pListHead=NULL;
    }
    //删除的是尾节点，并且不是头结点
    else
    {
        ListNode * tmp= *pListHead;
        while(tmp != NULL && tmp->m_pNext!=pToBeDeleted )
            tmp=tmp->m_pNext;
        if(tmp)
            tmp->m_pNext=NULL;
    }

}

void print_list(ListNode *head)
{
    ListNode *tmp=head;
    if(tmp==NULL)
        cout<< "List is empty"<<endl;
    while(tmp!=NULL)
    {
        cout<<tmp->m_nValue<< " ";
        tmp=tmp->m_pNext;
    }
    cout<<endl;
}

int main()
{
    ListNode p1;
    ListNode p2;
    ListNode p3;
    ListNode p4;
    ListNode p5;
    ListNode p6;
    p1.m_nValue=1;
    p1.m_pNext=&p2;
    p2.m_nValue=2;
    p2.m_pNext=&p3;
    p3.m_nValue=3;
    p3.m_pNext=&p4;
    p4.m_nValue=4;
    p4.m_pNext=&p5;
    p5.m_nValue=5;
    p5.m_pNext=NULL;
    p6.m_nValue=6;
    p6.m_pNext=NULL;

    ListNode *head=&p1;
    //这种方式并没有删除对应的指针指向的节点，而是改变了他的值。删除了他的下一个节点。
    //可以更滑调用方式。
    print_list(head);
    //实际上删除的是p2;
    DeleteNode(&head,&p1);
    cout<<"delete p1:";
    print_list(head);
    DeleteNode(&head,&p5);
    //实际上删除的是p5;
    cout<<"delete p5:";
    print_list(head);
    DeleteNode(&head,&p3);
    //实际上删除的是p4;
    cout<<"delete p4:";
    print_list(head);
    DeleteNode(&head,&p1);
    //实际上删除的是p3;
    cout<<"delete p3:";
    print_list(head);
    DeleteNode(&head,&p1);
    //实际上删除的是p2;
    cout<<"delete p2:";
    print_list(head);
    cout << "Hello world!" << endl;
    return 0;
}

####