代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表

一、移除链表元素的思想

直接让前一个节点指向后一个节点即可

两种方法

第一种：直接删除
第二种：头删的时候，直接head=head->next

其实这两种方法都没有做到统一

第三种：虚拟头结点法
这样的话，咱们删除的时候，就是以统一的规则来进行删除啦！

二、203.移除链表元素

203.移除链表元素
法一：原始删除法

class Solution
{
public:
    ListNode *removeElements(ListNode *head, int val)
    {
        // 头删
        while (head != nullptr && head->val == val)
        {
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
        }
        // 接下来不是头删，正常的中间删除
        ListNode *cur = head;
        while (cur != nullptr && cur->next != nullptr)
        {
            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

1、while(head!=nullptr && head->val == val)？

注意使用while 而不是 if ，因为会有特殊情况，持续删除头结点的情况，所以使用外while。

2、if(cur->next->val==val)

我们是使用的cur的next的值来判断是不是我们想要删除的val的。如果我们直接使用cur的值来判断的话，我们是不好来找到当前节点的上一个节点，从而链接起来的。

法二：虚拟头结点法

class Solution
{
public:
    ListNode *removeElements(ListNode *head, int val)
    {
        // 虚拟头结点来删除
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy; // 为啥从dummy起始？
        while (cur->next != nullptr)
        {
            if (cur->next->val == val)// 为啥用cur->next->val 作为判断？
            {
                cur->next = cur->next->next;
            }
            else
            {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1、ListNode *cur = dummy; // cur为啥从dummy起始？

而不是cur=head？
我们删除链表元素一定要知道上一个元素的指针是啥，我们删的是cur->next->val。

2、while (cur->next != nullptr)

遍历的时候，我们要判断的是cur->next->val，所以我们while (cur->next != nullptr) 要这么写。

3、if (cur->next->val == val)// 为啥用cur->next->val 作为判断？

我们是使用的cur的next的值来判断是不是我们想要删除的val的。如果我们直接使用cur的值来判断的话，我们是不好来找到当前节点的上一个节点，从而链接起来的。

4、为啥return dummy->next;

因为return head；有可能head已经被删除了。

三、707.设计链表

707.设计链表

统一使用虚拟头结点的方式，让我们的操作统一化。
我们还需要一个虚拟头节点_dummy作为头节点，和一个_size参数保存有效节点数。注意题目下标从0开始。

一定要注意：我们的临时变量定义cur=_dummy，操作的是cur->next，这样我才能方便的增加、删除，这才是对应到我们的第index（或者说第n个节点）。

class MyLinkedList
{
public:
    // 定义链表节点结构体
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int val) : val(val), next(nullptr) {}
    };
    MyLinkedList()
    {
        // 定义虚拟头结点
        _dummy = new ListNode(-1);
        _size = 0;
    }


// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
// 注意 index和_size差值为1
    int get(int index)
    {
        if (index > (_size - 1) || index < 0)
        {
            return -1;
        }
        ListNode *cur = _dummy->next; // 从头开始遍历寻找
        // 注意下标从0开始
        while (index)
        {
            cur = cur->next;
            index--;
        }
        return cur->val;
    }

    void addAtHead(int val)
    {
        ListNode *newnode = new ListNode(val);

        // 这两步顺序不能交换
        newnode->next = _dummy->next;
        _dummy->next = newnode;

        _size++;
    }

    void addAtTail(int val)
    {
        ListNode *newnode = new ListNode(val);
        // 找尾
        ListNode *cur = _dummy; // 为啥从dummy开始？
        while (cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = newnode;
        _size++;
    }

	
	// 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val)
    {
        if (index > _size)
            return;
        if (index < 0)
            index = 0;
            
        // 一定要找到第index个节点的前驱
        ListNode *newnode = new ListNode(val);
        ListNode *cur = _dummy;
        // 遍历找到第n个节点
        while (index--)
        {
            cur = cur->next;
        }
        // 这下面两步顺序也是不能换的
        newnode->next = cur->next;
        cur->next = newnode;
        _size++;
    }

    void deleteAtIndex(int index)
    {
        if (index < 0 || index >= _size)
        {
            return;
        }
        ListNode *cur = _dummy;
        // 遍历找到第n个节点
        while (index--) // 当index=0时，while循环就不会执行了
        {
            cur = cur->next;
        }
        ListNode *tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        _size--;
    }

private:
    int _size;
    ListNode *_dummy;
};
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、头插顺序不能变

2、addAtTail 中ListNode * cur=_dummy;// 为啥从dummy开始？

因为有可能刚刚开始没有元素，相当于在dummy后插入。

3、注意index与size之间的关系，他们差值为1

四、206.反转链表

206.反转链表
面试中经常出现

双指针法

// 双指针
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *cur = head;
        ListNode *pre = nullptr;
        while (cur != nullptr)
        {
            ListNode *tmp = cur->next;
            cur->next = pre; // 反转操作
            // 下面两步不能换顺序
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1、为啥要这样初始化？

因为这样初始化，直接让咱们的反转后的尾节点直接执行nullptr了。

2、while( ? ) 循环结束调条件是啥

就是cur为空就结束了，最后一步，不再需要nullptr指向pre了，没有意义。while(cur)就行了。

3、为啥需要每次进入循环都要定义一个tmp临时变量？

因为这样可以方便更新cur，反转后，cur无法后移指向下一个节点，tmp保存cur->next，趁着pre和cur还连着的时候先保存下来，然后就可以赋值了，一定要先移pre，后移动cur。

递归法

class Solution
{
public:
    // 子函数
    ListNode *reverse(ListNode *cur, ListNode *pre)
    {
        if (cur == nullptr)
            return pre;           // 2.终止条件就是cur指向nullptr
        ListNode *tmp = cur->next;
        cur->next = pre;          // 3.反转操作
        return reverse(tmp, cur); // 4、进入下一层循环(递归) 谁赋值给cur？ 谁赋值给pre？
    }

    ListNode *reverseList(ListNode *head)
    {
        return reverse(head, nullptr); // 1.head赋值给cur，nullptr赋值给pre
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

从后往前翻转指针指向 递归

• 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作last
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的next指针指向当前节点。
• 同时让当前结点的neat指针指向NULL，从而实现从链表尾部开始的局部反转
• 当递归函数全部出栈后，链表反转完成。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16