先补一下链表使用C++语言的相关实现，概念知识在上一片博文：
学习文档：链表的C++实现
基本结构
1
2
3
4
5
6
7
8
9
10
11
12
13
| template<typename T>
struct Node {
T _value;
Node<T> *_next;
Node() { _next = NULL; }
Node(const T &val) { _value = val; _next = NULL; }
T &value() { return _value; }
Node<T> *next() { return _next; }
void set_next(Node<T> *next) { _next = next; }
};
|
元素值的访问器 value() 返回的是成员变量 _value 的引用，所以只要这一个访问器就能同时满足外部程序对元素值进行读写的功能要求，例如：
1
2
3
4
| Node<int> n(2);
int v = n.value();
n.value()--;
n.value() = 3 * 3;
|
元素增删
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
|
template<typename T>
struct LinkedList {
void push_front(const T &val);
void insert(const T &val, const LinkedList<T>::Indicator prev);
private:
struct _Node;
_Node *_head;
size_t _size;
struct Indicator {
_Node *_ptr;
};
};
template<typename T>
void LinkedList<T>::push_front(const T &val)
{
LinkedList<T>::_Node *new_node = new LinkedList<T>::_Node(val);
new_node->_next = _head->_next;
_head->_next = new_node;
++_size;
}
template<typename T>
void LinkedList<T>::insert(const T &val, const LinkedList<T>::Indicator prev)
{
LinkedList<T>::_Node *new_node = new LinkedList<T>::_Node(val);
new_node->_next = prev._ptr->_next;
prev._ptr->_next = new_node;
++_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
|
template<typename T>
struct LinkedList {
void pop_front();
void erase(LinkedList<T>::Indicator prev);
void clear();
private:
struct _Node;
_Node *_head;
size_t _size;
struct Indicator {
_Node *_ptr;
};
};
template<typename T>
void LinkedList<T>::pop_front()
{
if (_size == 0) return;
LinkedList<T>::_Node *node = _head->_next;
_head->_next = node->_next;
delete node;
--_size;
}
template<typename T>
void LinkedList<T>::erase(LinkedList<T>::Indicator prev)
{
if (!prev._ptr || !prev._ptr->_next) return;
LinkedList<T>::_Node *node = prev._ptr->_next;
prev._ptr->_next = node->_next;
delete node;
--_size;
}
template<typename T>
void LinkedList<T>::clear()
{
LinkedList<T>::_Node *p = _head->_next, *next;
while (p) {
next = p->_next;
delete p;
p = next;
}
_size = 0;
_head->_next = NULL;
}
|
题解
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
|
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while(head != NULL && head->val == val) {
ListNode* tmp = head;
head = head->next;
delete tmp;
}
ListNode* cur = head;
while(cur != NULL && cur->next != NULL) {
if(cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else cur = cur->next;
}
return head;
}
};
|
代码逻辑
删除头节点中所有值等于 val 的节点：
while (head != NULL && head->val == val)：只要头节点存在且值等于 val，就删除头节点。ListNode* tmp = head; head = head->next; delete tmp;：保存当前头节点，更新头节点指针，然后删除原头节点。
删除链表中间部分值等于 val 的节点：
ListNode* cur = head;：初始化 cur 指针，指向当前节点。while (cur != NULL && cur->next != NULL)：遍历链表，直到 cur 或其下一个节点为 NULL。if (cur->next->val == val) ：如果 cur 的下一个节点值等于 val，则删除该节点。
返回值
return head;：返回更新后的链表头节点指针。
为什么需要 tmp
定义一个 tmp 变量是为了安全地删除节点。删除节点时，需要先保存该节点的地址，以便在更新指针后能够正确地释放该节点的内存。如果直接修改指针而不保存节点地址，可能会导致内存泄漏或访问已经释放的内存。
LeetCode 官方题解写的挺好的，跟着敲了一遍，熟悉一下链表增删改查等相关操作。
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 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
| class MyLinkedList {
public:
MyLinkedList() {
this->size = 0;
this->head = new ListNode(0);
}
int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode *cur = head;
for (int i = 0; i <= index; i++) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size, val);
}
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
index = max(0, index);
size++;
ListNode *pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
ListNode *toAdd = new ListNode(val);
toAdd->next = pred->next;
pred->next = toAdd;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode *pred = head;
for (int i = 0; i < index; i++) {
pred = pred->next;
}
ListNode *p = pred->next;
pred->next = pred->next->next;
delete p;
}
private:
int size;
ListNode *head;
};
|
206. 反转链表【简单】
个人思路
两个方法：
定义一个新的链表，然后找到原链表的最后一个元素，作为新链表的头节点(
- 发现这种方法反而很复杂，因为链表找最后一个元素很麻烦，而且单链表是不知道前一个元素是什么的，因此无论时间还是空间都比第二种更复杂
第二种，把所有链表的指针原地反转即可，如图：
题解（双指针法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while(curr != NULL) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
|
个人问题
