C++ 用单、双链实现链表数据结构，LeetCode题_c c++ 双向链表插入一个节点 leetcode

LeetCode原题链接：707.设计链表

1 单链表实现

// 定义单链表结构
struct LinkNode {
    int value;
    LinkNode *next;

    LinkNode() : value(0), next(nullptr) {}

    explicit LinkNode(int v) : value(v), next(nullptr) {}

    LinkNode(int v, LinkNode *n) : value(v), next(n) {}
};

class MyLinkedList {
private:
    int size_;  // 链表长度
    LinkNode *sentry_;  // 哨兵：非实头结点，主要用于确认边界

public:
    MyLinkedList() {
        sentry_ = new LinkNode(-1);
        size_ = 0;
    }

    /*获取链表中第 index 个节点的值。如果索引无效，则返回-1。*/
    int get(int index) {
        if (index < 0 || index >= size_) {  // 无效索引则返回-1
            return -1;
        }
        LinkNode *p = sentry_->next;  // 临时指针
        while (index--) {  // index--：减到0的时候表示到了index下标那个数
            p = p->next;  // 指针指向下一个元素
        }
        return p->value;
    }

    /*在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。*/
    void addAtHead(int val) {
        LinkNode *newNode = new LinkNode(val);
        newNode->next = sentry_->next;
        sentry_->next = newNode;
        size_++;
    }

    /*将值为 val 的节点追加到链表的最后一个元素。*/
    void addAtTail(int val) {
        LinkNode *newNode = new LinkNode(val), *p = sentry_;
        while (p->next != nullptr) {
            p = p->next;
        }
        p->next = newNode;
        size_++;
    }

    /* 在链表中的第index个节点之前添加值为val的节点。
     * 如果index等于链表的长度，则该节点将附加到链表的末尾。
     * 如果index大于链表长度，则不会插入节点。
     * 如果index小于0，则在头部插入节点。*/
    void addAtIndex(int index, int val) {
        if (index > size_) {
            return;
        }
        LinkNode *newNode = new LinkNode(val), *p = sentry_;
        while (index--) {
            p = p->next;
        }
        newNode->next = p->next;
        p->next = newNode;
        size_++;
    }
    
    /*如果索引 index 有效，则删除链表中的第 index 个节点。*/
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size_) {
            return;
        }
        LinkNode *p = sentry_;
        while (index--) {
            p = p->next;
        }
        LinkNode *tempNode = p->next;
        p->next = tempNode->next;
        delete tempNode, tempNode = nullptr;
        size_--;
    }
};
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

提交结果：

单链表效率慢了点，因为无法直接定位到最后一个节点，所以当每次需要后插入的时候，都需要遍历完全部元素。下面用双链表实现，提高效率。

2 双链表实现

// 双链表
struct DoubleLinkList {
    int value;
    DoubleLinkList *prev, *next;

    DoubleLinkList() : prev(nullptr), value(0), next(nullptr) {}

    explicit DoubleLinkList(int val) : prev(nullptr), value(val), next(nullptr) {}

    DoubleLinkList(DoubleLinkList *p, int val, DoubleLinkList *n) : prev(p), value(val), next(n) {}
};

class MyLinkedList {
private:
    int size_;
    DoubleLinkList *sentry_head, *sentry_tail;

public:
    MyLinkedList() {
        size_ = 0;
        sentry_head = new DoubleLinkList(nullptr, -1, nullptr);  // 哨兵头
        sentry_tail = new DoubleLinkList(sentry_head, -1, nullptr);  // 哨兵尾
        sentry_head->next = sentry_tail;
    }

    /*获取链表中第 index 个节点的值。如果索引无效，则返回-1。*/
    int get(int index) {
        if (index < 0 || index >= size_) {  // 如果索引无效，则返回-1
            return -1;
        }
        DoubleLinkList *p;
        if (index < size_ / 2) {  // 如果要查找的index小于链表长度的一半，则从前找起
            p = sentry_head->next;  // 临时指针指向哨兵头下一节点
            while (index--) {
                p = p->next;
            }
        } else {  // 否则index大于链表长度的一半，则从后找起
            p = sentry_tail->prev;  // 临时指针指向哨兵尾上一节点
            int count = size_ - 1;
            while (count-- != index) {
                p = p->prev;
            }
        }
        return p->value;
    }

    /*在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。*/
    void addAtHead(int val) {
        // 创建新节点，默认把哨兵头作为新节点的上一结点，把哨兵头下一节点作为新节点下一节点
        DoubleLinkList *newNode = new DoubleLinkList(sentry_head, val, sentry_head->next);
        sentry_head->next->prev = newNode;  // 把哨兵头下一结点的上一节点指向新节点
        sentry_head->next = newNode;  // 把哨兵头的下一结点指向新节点
        size_++;  // 链表长度+1
    }

    /*将值为 val 的节点追加到链表的最后一个元素。*/
    void addAtTail(int val) {
        // 创建新节点，默认把哨兵尾上一节点作为新节点的上一节点，新节点下一节点指向哨兵尾
        DoubleLinkList *newNode = new DoubleLinkList(sentry_tail->prev, val, sentry_tail);
        sentry_tail->prev = newNode;  // 把哨兵尾的上一节点指向新节点
        newNode->prev->next = newNode;
        size_++;  // 链表长度+1
    }

    /* 在链表中的第 index 个节点之前添加值为 val 的节点。
     * 如果 index 等于链表的长度，则该节点将附加到链表的末尾。
     * 如果 index 大于链表长度，则不会插入节点。
     * 如果 index 小于 0，则在头部插入节点。*/
    void addAtIndex(int index, int val) {
        if (index > size_) {
            return;
        }
        DoubleLinkList *newNode = new DoubleLinkList(val), *p;
        if (index < size_ / 2) {  // 如果 index 小于链表长度的一半，则从哨兵头开始
            p = sentry_head->next;  // 临时指针 p 是寻找 index 的指针
            while (index--) {
                p = p->next;
            }
        } else {  // 如果 index 大于链表长度的一半，则从哨兵尾开始
            p = sentry_tail;  // 临时指针 p 是寻找 index 的指针
            int count = size_;
            while (count-- != index) {
                p = p->prev;
            }
        }
        // 此时的 p 指针指向的是 index 的节点
        newNode->prev = p->prev;  // 将新节点上一节点指向 index 节点的上一节点
        newNode->next = p;  // 将新节点下一节点指向 index 节点
        p->prev->next = newNode;  // index 节点上一节点的下一节点指向新节点
        p->prev = newNode;  // index 节点上一节点指向新节点
        size_++;
    }

    /*如果索引 index 有效，则删除链表中的第 index 个节点。*/
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size_) {
            return;
        }
        DoubleLinkList *p;
        if (index < size_ / 2) {
            p = sentry_head->next;
            while (index--) {
                p = p->next;
            }
        } else {
            p = sentry_tail->prev;
            int count = size_ - 1;
            while (count-- != index) {
                p = p->prev;
            }
        }
        DoubleLinkList *tempNode = p;
        p->prev->next = p->next;
        p->next->prev = p->prev;
        size_--;
        delete tempNode, tempNode = nullptr;
    }
};
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

提交结果：

可以发现双链表的效率高于单链表的效率，至于内存消耗，是个迷。