代码随想录算法训练营第三天|203、707、206

链表

链表的初始化

在Leecode上做题，一般都会给链表的定义

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
1
2
3
4
5
6
7

用到的就是链表的初始化列表，单链表分数值域和指针域

链表题目还有一个关键，就是需要判断当前节点和要操作的节点是不是NULL

Leecode203. 移除链表元素

链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

经典链表题目。同时处理方式也分两种：第一种是基本的链表处理方式，第二种是需要设置一个虚拟头结点

先描述基本方法，然后就可以搞懂为什么会有虚拟节点这种优化方法了

因为若是不设置虚拟头结点，对于单链表，我们是不能直接在这个元素上做删除的，因为单链表没有记录当前节点的上一个元素在哪？若是我们在当前元素上做删除操作，那么结果就是无法定位到这个元素及这个元素的下一个元素，所以我们使用的操作一般都是在目标元素的前一个元素上删除目标元素——那么问题就来了，头结点是没有上一个元素的，也因此导致头结点的删除方式和一般节点不同，我们需要有两套处理手段：

version1 朴素方法

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
            // 首先考虑最基本的写法：
            // 因为处理头结点和其他节点的方式不一样，所以我们要先把头结点给处理好
            // 那么如何处理头结点呢？考虑必须处理头结点的场合：
            // 头结点的val值和tar值是一样的，所以必须处理，但是有可能上来就给一个空表，所以要先判断头结点不为空，并且由于和目标值相等的头结点不一定只有一个，所以我们用while循环左
            while(head != NULL && head -> val == val)
            {
                // 然后就是头结点的删除操作，我们是直接在这个节点上删除的，所以删除之前要记录这个节点指向其后的指针
                ListNode *tmp = head ;
                head = head -> next;
                delete tmp;
            } // 因为我们要保存并且最后返回head，所以用了中间变量指向之前的head
            // 然后我们考虑删除普通节点中的元素,怎么做？
            // 是需要遍历的，也就是说需要从head之后的节点开始一直遍历到当前节点的下一个节点为NULL
            // 所以while条件就是当前指针不为空，当前指针是需要当场定义的，我们刚从上面得到了处理后的head，那么当前指针就是head -> next
            // 但是很有可能处理完毕头结点后整个链表都是空的了，所以我们还需要定义cur = head，并且判断cur != NULL之后才能继续后面的循环
            ListNode *cur = head;
            while(cur!= NULL && cur->next != NULL) // 我们删除一般节点的方式是通过其前一个节点来删除之，所以要判断后续节点是不是空
            {
                // 注意，我们处理完毕头节点之后遇见的第一个合法指针的val是一定不等于val的，否则其就会被当做头结点处理掉，所以判断删除节点的条件是cur->next->val == val
                if(cur->next -> val == val)
                {// 然后对当前节点的下一个节点进行删除操作
                    ListNode *tmp = cur -> next;
                    cur->next = cur->next->next;
                    delete tmp;
                } 
                else cur = cur->next;
            }
        return head;
    }
};
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

此法中即使知道处理完head后第一个普通节点一定不满足删除的条件，但是还需要判断当前指针是不是空指针，因为有可能处理完头结点后整个链表都是空的

version2 虚拟头结点

有了虚拟头结点删除头结点和删除普通节点的方式就一毛一样

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 现在我们考虑虚拟指针的做法
        // 首先将虚拟指针定义出来，并将虚拟指针的next指向当前的head
        // 然后就可以循环来删除元素了

        ListNode * dummy_head = new ListNode(); // 因为要新增加一个指针，所以要new一个出来
        dummy_head ->next = head;
        ListNode * cur = dummy_head;
        // 头指针可以动吗？因为我最后要返回的实际上是dummy_head->next,所以我们不可以用dummy_head去循环，
        // 并且为了最后删除dummyhead，我们必须定义出dummyhead之后就再设置一个cur指向dummy_head
        while(cur -> next != NULL) // 循环过程中我们保存dummy_head，就像之前在普通方法中处理普通节点一样
        {
            if(cur -> next -> val == val)
            {
                ListNode *tmp = cur->next;
                cur ->next = cur->next->next;
                delete tmp;
            }
            else {cur = cur->next;} // 为什么我们一直在遍历cur，但是最后返回dummy_head -> 是可行的呢？因为虚拟头结点一定是合法的，遍历的过程就是改变虚拟头结点后的指针的过程
        }
        // 最后还是通过定义中间变量以便删除dummy_head
        head = dummy_head->next;
        delete dummy_head;
        return  head;
    }
};
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

比较容易混乱的是对于虚拟头结点的操作：

1. 开始的时候我们会设置一个虚拟头结点，但是这个头结点是不参与循环的，仅仅是记录对的位置。

2. 同时参与循环的头结点刚开始就被赋值和这个虚拟头结点指向同样的位置了，循环完毕就没有用了

3. 最后我们还要删除这个虚拟头结点，就让函数形参的head直接替代我们定义的虚拟头结点，然后将虚拟头结点delete掉就可

Leecode707. 设计链表

链接：https://leetcode.cn/problems/design-linked-list/

这道题目还是比较细致的，一共考察了五种操作，分别是：获取链表中的元素、头插、尾插、普通插入和删除元素

其中比较易错的就是后两个函数，并且对于普通插入和删除操作，比较好的方式是定义一个虚拟头结点

class MyLinkedList {
public:
    struct LinkNode 
    {
        LinkNode* next;
        int val;
        LinkNode(int x):val(x),next(nullptr){} // 利用初始化列表最后不需要加分号
    };

    MyLinkedList() { // 初始化链表
        _dummy_head = new LinkNode(0); // 只有虚拟头结点肯定长度为0
        _size = 0;
    }
    
    int get(int index) {
        // 应该是需要定义一个节点用来指向_dummy_head的
        LinkNode * temp = _dummy_head;

        // 考虑过index是0的情况了吗
        if(index <0 || index >= _size) return -1;
        
        index += 1;

        while(index--) // 第几个元素，不是从0开始的索引值
        {
            if(temp -> next != NULL)
            temp = temp->next;
        }
        return temp->val;
    }
    
    void addAtHead(int val) {
        // 前插元素有两种情况，第一种就是目前链表中除了虚拟头结点外再没有其他节点，还有一种情况就是有其他节点
        LinkNode * add = new LinkNode(val);
        add -> val = val;

        LinkNode * temp = _dummy_head ->next;
        add->next = temp;
        _dummy_head->next = add;

        _size ++;
    }
    
    void addAtTail(int val) {
        // 其实也是循环遍历到最后一个元素，然后操作指针增加元素
        // 所以我们还是要定义一个指针刚开始指向的是头结点
        LinkNode *temp = _dummy_head;
        while(temp -> next != NULL) temp = temp->next;

        LinkNode *addtail = new LinkNode(val);
        temp ->next = addtail;
        addtail -> next = NULL;

        _size ++;
    }
    
    void addAtIndex(int index, int val) { // 这个跟在addhand或者addtail后面就会有问题
        // index是从0开始的
        if(index == _size)  {addAtTail(val);}
        else if(index <= 0) {addAtHead(val);}

        else if(index > 0 && index<_size) //这里有问题
        {
            LinkNode * temp = _dummy_head;
            // 因为index就是从0开始的，所以正常移动就会到达目标元素的上一个节点
            while(index--)
            {
                // 刚好在index--后的位置插入即可
                if(temp -> next != NULL)
                temp = temp->next; // 如果index = 1，那么此时指向的是第一个节点
            }

            // 所以此时到达的元素应该是要插入位置的前一个元素
            // 插入元素，让前面的元素指向自己，让自己指向前面元素的next
            LinkNode * insert = new LinkNode(val);

            // 应该是新节点左侧连接temp，新节点右侧连接temp->next
            insert -> next = temp->next; // 这里错了！！！
            temp -> next = insert;

            _size ++;
        }
        return;
    }
    
    void deleteAtIndex(int index) {
        if(index >= 0 && index < _size)
        {
            LinkNode * temp = _dummy_head;
            while(index--)
            {
                // 刚好在index--后的位置插入即可
                if(temp -> next != NULL)
                temp = temp->next;
            }

            // 删除元素
            LinkNode * tar = temp->next;
            temp -> next = temp ->next->next;
            delete tar;

            --_size;
        }
    }
    private:
    LinkNode * _dummy_head;
    int _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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

题目仅仅给了我们一个大致框架，没有限制是单链表还是双向链表，也就是说我们可以定义单链表，也可以定义双向链表，在这里我们选择使用单链表：同时在私有成员中定义虚拟头结点和整个链表的长度，在写函数之前还要完成初始化列表的函数，其实和我们之前接触的初始化方法一毛一样

get方法

我在这里犯错了，没有想清楚什么时候应该删除定义的节点，什么时候不应该删除。

我们定义这些方法的时候，不可避免地要先定义一个指针指向dummy_head，后续遍历列表。所以在get函数中也是这样，我们定义了指针temp指向dummy_head，之后我们用temp去遍历链表而不改变dummy_head的值，因为temp指针的位置都是有效的，所以不可以delete。那么什么时候能用到delete操作呢？删除节点。new的操作也是同理，只在new虚拟节点或者头插尾插或者中间插入等需要开辟新空间的时候用到了new，其他情况下又不需要开辟新的空间，也就没有必要new

而且因为index是从0开始的，为了代码的统一性，进入while循环之前先让index++，这样即使index是0，也可以让temp走到头结点并且返回头结点的值

addAtIndex方法

这个方法也出现了一些bug，首先需要明白当index<=0的时候就是头插，当index==_size的时候就是尾插，余下的情况就比较复杂：若待插入元素的index = 1，那么应当插入到索引为0和索引为1的元素中间，那么target处的next指针就应该是元素1的next指针，而不是next->next，同时元素1的next指针指向的是target

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wu1TllNW-1668779680977)(算法笔记.assets/image-20221118190633049.png)]

Leecode206. 反转链表

链接：https://leetcode.cn/problems/reverse-linked-list/

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 这个题是没有虚拟节点的，也不是双向链表，所以我们做的时候要时刻记录每个节点的前向节点
        // 也没有必要定义虚拟头结点，因为按理来说第一个头结点翻转之后应该指向null

        // 我们的思路是定义两个指针，分别指向前面的节点pre和当前节点now，注意初始情况下pre节点是NULL
        ListNode *pre = nullptr;
        ListNode *now = head;
        // 在开始循环之前需要保证now和不为空，当now开始就为空说明是空表
        
        // 按理来说也应该保证now -> next!=NULL，但这种情况显然是最后一个元素，分开写两个if-else没有必要
        while(now != NULL)
        {
            ListNode * temp = now->next;
            now -> next = pre;

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