代码随想录算法训练营第三天|LeetCode 203.移除链表元素 、707.设计链表 、206.反转链表

LeetCode 203.移除链表元素

题目链接：203.移除链表元素

链表的定义：

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
1
2
3
4
5
6

ListNode(int x) : val(x), next(NULL) {} 
1

此段代码是构造函数初始化列表，以一个冒号开始，接着是以逗号分隔数据成员列表，每个数据成员后面跟一个放在括号中的初始化式，初始化列表仅在构造函数中有效，不能用于其他函数。

等价于：

ListNode(int x) {
    val = x;
    next = nullptr;
}

1
2
3
4
5

注意：

如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值。

思路：
1、设置一个虚拟头节点，方便对头节点进行操作
2、遍历往后找到符合条件的节点删除即可，记得释放空间
3、最后，将头节点换回原来的头节点，将虚拟头节点释放即可

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //设置一个虚拟头节点，方便对链表所有节点进行统一操作
        ListNode* virtual_Head = new ListNode(0); // 设置一个虚拟头节点
        virtual_Head -> next = head;  // 虚拟头节点指向真实头节点
        //以下对链表所有元素都可以进行统一操作
        ListNode* cur = virtual_Head;
        while (cur -> next != nullptr) {     // 遍历终止条件
            if (cur -> next -> val == val) {
                //进行删除节点操作
                ListNode* tmp = cur -> next;
                cur -> next = cur -> next -> next;
                delete tmp;
            }
            //不符合往后遍历即可
            else{
                cur = cur -> next;
            }
        }
        //将头节点换成原来的头节点
        head = virtual_Head -> next;
        //删除原来的头节点
        delete virtual_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

LeetCode 707. 设计链表

题目链接：203.移除链表元素

思路：此题考查链表的基本构造，可以打好基础，充分理解好链表的基本知识，具体实现细节在注释里
** 注意：最后两个需求，根据index插入元素和删除元素的if有所不同**
1、根据index插入元素插入，if (index > _size || index < 0) { return; }
2、根据index删除元素，if (index >= _size || index < 0) { return; }

class MyLinkedList {
public:
    //定义链表结构体
    struct LinkedNode{
        int val; //节点对应的值
        LinkedNode *next; //指向当前节点的下一节点的指针
        //节点的构造函数
        LinkedNode(int val) : val(val),next(nullptr){}
    };
    //初始化链表
    MyLinkedList() {
        //创建一个虚拟头节点
        virtul_Head =  new LinkedNode(0);
        _size = 0;
    }
    
    //获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = virtul_Head -> next;
        //遍历终止条件
        while(index){
            cur = cur -> next;
            index --;
        }
        return cur -> val;
    }
    
    //创建一个新节点，将新节点指向头节点，虚拟头节点指向新节点
    void addAtHead(int val) {
        //创建这个新节点
        LinkedNode* new_Node = new LinkedNode(val);
        new_Node -> next = virtul_Head -> next;
        virtul_Head -> next = new_Node;
        _size ++;
    }
    
    //创建一个新节点和一个当前指针，首先遍历到最后，然后将最后一个节点指向这个新节点
    void addAtTail(int val) {
        LinkedNode* new_Node = new LinkedNode(val);
        LinkedNode* cur = virtul_Head;
        while (cur -> next !=nullptr) {
            cur = cur -> next;
        }
        cur -> next = new_Node;
        _size++;
    }
    
    //注意：这里的以下的while(index)
    void addAtIndex(int index, int val) {
        //这里的index < 0很巧妙，可以直接不用操作，因为后面怎么都会进行一次插入节点
        //注意这里的if()操作中index的细节，=_sized的操作也一起并到里面了
        if (index > _size || index < 0) {
            return;
        }
        LinkedNode* cur = virtul_Head;
        while (index) {
            cur = cur -> next;
            index --;
        }
        //创建新节点，进行插入
        LinkedNode* new_Node =  new LinkedNode(val);
        new_Node -> next = cur -> next;
        cur -> next = new_Node;
        _size ++;
    }
    
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = virtul_Head;
        while (index) {
            cur = cur -> next;
            index --;
        }
        //进行删除节点操作
        //创建一个临时节点，指向要删除的节点
        LinkedNode* tmp = cur -> next;
        cur -> next = cur -> next -> next;
        delete tmp;
        _size --;
    }

    //打印链表
    void printList(){
        //遍历打印即可
        LinkedNode* cur = virtul_Head;
        while (_size) {
            cout << cur -> next -> val << " ";
            cur = cur -> next;
            _size --;
        }
        cout << endl;
    }
private:   
    int _size;
    LinkedNode* virtul_Head;
};

/**
 * 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
110
111

LeetCode 206.反转链表

题目链接：206.反转链表

思路：此题较为简单，后续有时间再看递归解法吧
1、使用双指针进行遍历，不停的让后面的节点指向前面的节点即可

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* tmp;
        while (cur) {
            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
20
21
22
23
24
25