寸_铁

这个屌丝很懒，什么也没留下！

热门标签

算法力扣刷题记录七【707. 设计链表】

作者：寸_铁 | 2024-07-10 12:22:28

踩

前言

记录七：力扣【707. 设计链表】
完成链表索引，增删操作。

一、题目阅读和理解

题目阅读

你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() ;//初始化 MyLinkedList 对象。
int get(int index) ;//获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) ;//将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) ;//将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) ;//将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将不会插入到链表中。
void deleteAtIndex(int index) ;//如果下标有效，则删除链表中下标为 index 的节点。
1
2
3
4
5
6

示例：

输入:

["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
1
2

输出

[null, null, null, null, 2, null, 3]
1

解释

MyLinkedList myLinkedList = new MyLinkedList();			//创建对象
myLinkedList.addAtHead(1);	//头部添加元素1
myLinkedList.addAtTail(3);		//尾部添加元素3
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 第一个节点，元素值为2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 第一个节点，元素值为3
1
2
3
4
5
6
7

二、第一次尝试

测试通过代码

class MyLinkedList {
private:
    ListNode* head = nullptr;
public:
    MyLinkedList() {
        ListNode* head  = nullptr;
    }
    
    int get(int index) {
        ListNode* cur = head;
        int num = 0;//计数

        while( cur != nullptr){
            if(num == index){
                return cur->val;
            }
            cur = cur->next;
            num++;
        }
        return -1;
    }
    
    void addAtHead(int val) {
        if(head == nullptr){
            head  = new ListNode(val);
            return;
        }else{
             ListNode* node = new ListNode(val);
            node->next = head;
            head = node;
            return;
        }
    }
    
    void addAtTail(int val) {
        ListNode* cur = head;
        if(cur == nullptr){
            ListNode* node = new ListNode(val);
            head = node;
            return;
        }
        while(cur != nullptr){
            if(cur->next == nullptr){
                ListNode* node = new ListNode(val);
                cur->next = node;
                break;
            }else{
                cur = cur->next;
            }
            
        }
        
        
    }
    
    void addAtIndex(int index, int val) {
        ListNode *newnode = new ListNode(val);
        int num = 0;

        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node;
        while(cur!= nullptr ){
            if(num == index){
                newnode->next = cur->next;
                cur->next = newnode;
                break;
            }else{
                cur = cur->next;
                num++;
            }
        }
        head = dummy_node->next;
        delete dummy_node;

    }
    
    void deleteAtIndex(int index) {
        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node;
        int num = 0;

        while(cur != nullptr && cur->next != nullptr){
            if(num == index){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                break;
            }else{
                cur = cur->next;
                num++;
            }
        }
        head = dummy_node->next;
        delete dummy_node;
    }
};

//具体实例化方式和调用方式：
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
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

过程解释

（1）构造函数

MyLinkedList() {
        ListNode* head  = nullptr;
    }
    
1
2
3
4

调用 MyLinkedList myLinkedList = new MyLinkedList(); //创建对象时，需要一个头节点，是链表的入口，所以成员ListNode* head头指针应该得到初始化。一开始创建一个空链表，没有节点，所以ListNode* head = nullptr;赋为空。

（2）获取元素

int get(int index) {
        ListNode* cur = head;
        int num = 0;//计数

        while( cur != nullptr){
            if(num == index){
                return cur->val;
            }
            cur = cur->next;
            num++;
        }
        return -1;
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14

用一个cur来查找链表，从头节点开始；
并用num计数，看有没有到达目标节点；
由于不能操作空指针，所以while条件是( cur != nullptr)
if(num == index)，则返回节点的值。否则，cur后移。num++；
while结束，说明没有找到index，return -1.（因为题目说：下标无效都返回-1）
用边界条件判断逻辑是否正确：
- 如果head为空，不进入while循环，直接返回-1.（下标无效）
- 若只有一个节点，index=0，可以获得返回值；如果index=2，说明while循环退出，还没有return，所以最终return -1.（超出下标范围）

所以逻辑正确。

（3）添加头元素

void addAtHead(int val) {
        if(head == nullptr){
            head  = new ListNode(val);
            return;
        }else{
             ListNode* node = new ListNode(val);
            node->next = head;
            head = node;
            return;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

添加元素，第一步得创建一个元素，所以ListNode* node = new ListNode(val);
第二步找到head，因为head指向头节点，我多余一步考虑head是不是空；
如果是空，那么head = new ListNode(val);指向新节点，return；
如果不是空，先node->next = head;把新节点后继指向head；再让head换到新节点node：head = node;
最后return;

但是我发现：在else逻辑下，没有head->，说明即使head为空，我也没有访问空指针。那么可以合二为一，无需分开讨论，改进：

void addAtHead(int val) {
        // if(head == nullptr){
        //     head  = new ListNode(val);
        //     return;
        // }else{
            ListNode* node = new ListNode(val);
            node->next = head;
            head = node;
            return;
        //}
    }
1
2
3
4
5
6
7
8
9
10
11

（4）在链表尾部添加元素

    void addAtTail(int val) {
        ListNode* cur = head;
        if(cur == nullptr){
            ListNode* node = new ListNode(val);
            head = node;
            return;
        }
        while(cur != nullptr){
            if(cur->next == nullptr){
                ListNode* node = new ListNode(val);
                cur->next = node;
                break;
            }else{
                cur = cur->next;
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

先创建一个要添加的节点：ListNode* node = new ListNode(val);
找到cur->next == nullptr说明到达链表尾部。修改cur->next = node;

因为用到cur->next，说明cur不能为空。所以我初始考虑cur==nullptr情况，即空链表时：

  if(cur == nullptr){
          ListNode* node = new ListNode(val);
          head = node;
          return;
      }
1
2
3
4
5

再while(cur != nullptr)，找到链表尾部。

（5）在下标index之前添加元素

void addAtIndex(int index, int val) {
        ListNode *newnode = new ListNode(val);
        int num = 0;

        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node;
        while(cur!= nullptr ){
            if(num == index){
                newnode->next = cur->next;
                cur->next = newnode;
                break;
            }else{
                cur = cur->next;
                num++;
            }
        }
        head = dummy_node->next;
        delete dummy_node;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

为什么这里突然用上虚拟头节点？如果没有虚拟头节点：
- 添加操作肯定要cur->next，那么cur不能为空。如果cur = head;(初始)，得先判断cur是不是空；
- 如果cur是空，整个是空链表，index=0，也不好解释哪里有0号元素。
- 当index=0，在头节点之前加，得移动head，不用while(cur!= nullptr )；链表中间加，cur已经指向0，进入while(cur!= nullptr )判断的第一个index=1。所以需要看index是不是0。
所以统一用虚拟头节点，这样cur不会为空，并且index也不会错位。
第一步：要添加的节点先创建出来；并且有num计数，确定index位置；
第二步：创建虚拟头节点，dummy_node;并cur = dummy_node;
第三步：因为在cur后面加，所以用到cur->next，那么while条件是(cur!= nullptr )。
第四步：if(num == index)，添加操作。就可以break;结束循环，因为只加一个节点，已经完成工作。
第五步：如果num != index，cur后移。
第六步：改变head的位置，head = dummy_node->next;
第七步：delete dummy_node;
第八步：判断是不是index之间位置加入节点？用index=1，if判断一下，发现num和index没有错位。
第九步：当index超出长度，while循环结束，也没有用上newnode，的确没有添加，但是newnode此时创建的内存没有释放**（bug）**，所以用上了newnode，不需要delete（当前逻辑）；没有用上，需要delete newnode;（逻辑漏洞）。

改进：

    void addAtIndex(int index, int val) {
        ListNode *newnode = new ListNode(val);
        int num = 0;

        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node;
        while(cur!= nullptr ){
            if(num == index){
                newnode->next = cur->next;
                cur->next = newnode;
                break;
            }else{
                cur = cur->next;
                num++;
            }
        }
        if(num < index){	//注意这里。没用上newnode，需要释放本次调用创建的内存。
            delete newnode;
        }
        head = dummy_node->next;
        delete dummy_node;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（6）在下标index之前删除元素

void deleteAtIndex(int index) {
        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node;
        int num = 0;

        while(cur != nullptr && cur->next != nullptr){
            if(num == index){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                break;
            }else{
                cur = cur->next;
                num++;
            }
        }
        head = dummy_node->next;
        delete dummy_node;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路：用虚拟头节点统一删除操作。cur需要停在删除目标之前。

第一步：创建虚拟头节点，dummy_node;并cur = dummy_node;
第二步：num用来计数，判断有没有到达删除位置。
第三步：删除时，用到cur->next和cur->next->next赋值，所以cur和cur->next不能为空。
第四步：if(num == index)，符合条件，删除节点。循环就可以退出了，所以break;
第五步：else：后移cur。
最后改变head和delete dummy_node;
检查1：举例index=0，进到if(num == index)，的确删除0号元素；
检查2：index无效，如果小于0，没有删除操作。如果大于长度，while结束即可。没有需要释放的内存。
所以，通过。

改进代码（在过程解释后又有些改进的地方）

两个地方：一、添加头元素；二、在下标index之前添加元素

class MyLinkedList {
private:
    ListNode* head = nullptr;
public:
    MyLinkedList() {
        ListNode* head  = nullptr;
    }
    
    int get(int index) {
        ListNode* cur = head;
        int num = 0;//计数

        while( cur != nullptr){
            if(num == index){
                return cur->val;
            }
            cur = cur->next;
            num++;
        }
        return -1;
    }
    
    void addAtHead(int val) {	//多余if判断
        // if(head == nullptr){
        //     head  = new ListNode(val);
        //     return;
        // }else{
            ListNode* node = new ListNode(val);
            node->next = head;
            head = node;
            return;
        //}
    }
    
    void addAtTail(int val) {
        ListNode* cur = head;
        if(cur == nullptr){
            ListNode* node = new ListNode(val);
            head = node;
            return;
        }
        while(cur != nullptr ){
            if(cur->next == nullptr){
                ListNode* node = new ListNode(val);
                cur->next = node;
                break;
            }else{
                cur = cur->next;
            }
            
        }
        
        
    }
    
    void addAtIndex(int index, int val) {
        ListNode *newnode = new ListNode(val);
        int num = 0;

        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node;
        while(cur!= nullptr ){
            if(num == index){
                newnode->next = cur->next;
                cur->next = newnode;
                break;
            }else{
                cur = cur->next;
                num++;
            }
        }
        if(num < index){		//这里增加一段if
            delete newnode;
        }
        head = dummy_node->next;
        delete dummy_node;

    }
    
    void deleteAtIndex(int index) {
        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node;
        int num = 0;

        while(cur != nullptr && cur->next != nullptr){
            if(num == index){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                break;
            }else{
                cur = cur->next;
                num++;
            }
        }
        head = dummy_node->next;
        delete dummy_node;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
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

代码随想录学习

学习内容

（1）虚拟头节点

我是在函数操作（5）（6）在index之前添加/删除元素才考虑到dummy_node，在函数方便使用；
参考教程：直接class MyLinkedList中定义一个dummy_node，所有函数都可以用dummy_node操作。

（2）index
我没有先判断index在不在范围，而是先操作链表，如果index不在范围，最后while结束即可；
参考教程：定义int _size;可以先判断index在不在范围，不在范围就直接return。不用多余浪费时间循环链表。

总结：参考的方法更加统一方便。

重新写一遍，用新思路

我在public中多加了 ListNode* head;创建对象后，可以获取到链表的head，但是dummy_node是隐藏的（在private中）。

//单链表
class MyLinkedList {
private:
    ListNode* dummy_node;
    int _size;//链表节点数量
    
public:
    //struct ListNode{
    //    int val;
    //    ListNode* next;
    //    ListNode():val(0),next(nullptr){}
    //    ListNode(int i):val(i),next(nullptr){}
    //    ListNode(int i,ListNode* next):val(i),next(next){}
    //};
    ListNode* head;//可以加一个头节点
    MyLinkedList() {    //空链表
        dummy_node = new ListNode();
        head = dummy_node->next;
        _size = 0;
    }
    
    int get(int index) {
        if(index < 0 || index >= _size){    //大于等于_size，index才合法。
            return -1;
        }
        ListNode* cur = dummy_node->next;
        while(index--){ //先判断，后--
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode* newnode = new ListNode(val);
        newnode->next = head;
        dummy_node->next = newnode;
        head = dummy_node->next;        //  更改head的位置，始终是dummy_node->next
        _size++;
    }
    
    void addAtTail(int val) {
        ListNode* newnode = new ListNode(val);
        ListNode* cur = dummy_node;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newnode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index < 0 || index > _size){	//大于size，当等于size时，可以在尾部添加。
            return;
        }
        ListNode* newnode = new ListNode(val);
        ListNode* cur = dummy_node;
        int num = index;
        while(num--){
            cur=cur->next;
        }
        newnode->next = cur->next;
        cur->next = newnode;
        if(index == 0){ //head需要改变
            head = dummy_node->next;
        }
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= _size){ //_size是数量，所以最后一个有效的下标是 _size-1
            return;
        }
        ListNode* cur = dummy_node;
        int num = index;	//因为要用index判断head有没有改变。所以给num
        while(num--){
            cur = cur->next;
        }
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        if(index==0){   //删除0号，所以head改变。
            head = dummy_node->next;
        }
        _size--;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
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

总结

链表构建最好有一个虚拟头节点。

（欢迎指正，转载表明出处）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/806254