链表基础
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域，最后一个节点的指针域指向null（空指针的意思）。
移除链表元素
题目链接：203. 移除链表元素
题目描述：一个链表的头节点 head 和一个整数 val ，删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
虚拟头节点
时间复杂度：O(n) 空间复杂度：O(1)
题目思路：如果直接处理链表的话，需要考虑头节点，但是加入虚拟头节点就可以按照统一的方式去处理。
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* removeElements(ListNode* head, int val) {
ListNode* dummy=new ListNode(0);
ListNode* pre=dummy;
pre->next=head;
while(head)
{
if(head->val==val)
{
pre->next=head->next;
ListNode* tem=head;
head=head->next;
delete tem;
}
else
{
pre=head;
head=head->next;
}
}
return dummy->next;
}
};
|
直接操作
时间复杂度：O(n) 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
};
|
递归解法
时间复杂度：O(n) 空间复杂度：O(n)
题目思路：首先检查头节点的值是否为 val，如果是则移除头节点，答案即为在头节点的后续节点上递归的结果；如果头节点的值不为 val，则答案为头节点与在头节点的后续节点上递归得到的新链表拼接的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (head == nullptr) {
return nullptr;
}
if (head->val == val) {
ListNode* newHead = removeElements(head->next, val);
delete head;
return newHead;
} else {
head->next = removeElements(head->next, val);
return head;
}
}
};
|
反转链表
题目链接：206. 反转链表
题目描述：反转单链表，并返回反转后的链表。
双指针法
时间复杂度：O(n) 空间复杂度：O(1)
题目思路：定义cur和pre指针，pre初始化为NULL，cur指向head，然后反转链表，cur->next指向pre，按逻辑移动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tem;
ListNode* cur=head;
ListNode* pre=NULL;
while(cur)
{
tem=cur->next;
cur->next=pre;
pre=cur;
cur=tem;
}
return pre;
}
};
|
递归法
思路和双指针差不多，明天研究一下。
时间复杂度：O(n) 空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
return reverse(NULL, head);
}
};
|
设计链表
题目链接：707. 设计链表
题目描述：获取第index个节点的值，添加头节点，添加尾节点，在第 index 个节点之前添加值为 val 的节点，删除链表中的第 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
| class MyLinkedList {
private:
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val) : val(val), next(nullptr) {}
};
LinkedNode* dummyhead;
int size;
public:
MyLinkedList() {
dummyhead=new LinkedNode(0);
size=0;
}
int get(int index) {
if(index>(size-1) || index<0){
return -1;
}
LinkedNode* cur=dummyhead->next;
while(index--){
cur=cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next=dummyhead->next;
dummyhead->next=newNode;
size++;
}
void addAtTail(int val) {
LinkedNode* newNode=new LinkedNode(val);
LinkedNode* cur=dummyhead;
while(cur->next != NULL)
{
cur=cur->next;
}
cur->next=newNode;
size++;
}
void addAtIndex(int index, int val) {
if(index>size) return;
if(index<0) index=0;
LinkedNode* newNode=new LinkedNode(val);
LinkedNode* cur=dummyhead;
while(index--){
cur=cur->next;
}
newNode->next=cur->next;
cur->next=newNode;
size++;
}
void deleteAtIndex(int index) {
if(index>(size-1) || index<0){
return;
}
LinkedNode* cur=dummyhead;
while(index--)
{
cur=cur->next;
}
LinkedNode* tem=cur->next;
cur->next=cur->next->next;
delete tem;
size--;
}
};
|
虚拟头节点（双链表）
还未看，直接copy的
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
class MyLinkedList {
public:
struct DList {
int elem;
DList *next;
DList *prev;
DList(int elem) : elem(elem), next(nullptr), prev(nullptr) {};
};
MyLinkedList() {
sentinelNode = new DList(0);
sentinelNode->next = sentinelNode;
sentinelNode->prev = sentinelNode;
size = 0;
}
int get(int index) {
if (index > (size - 1) || index < 0) {
return -1;
}
int num;
int mid = size >> 1;
DList *curNode = sentinelNode;
if (index < mid) {
for (int i = 0; i < index + 1; i++) {
curNode = curNode->next;
}
} else {
for (int i = 0; i < size - index; i++) {
curNode = curNode->prev;
}
}
num = curNode->elem;
return num;
}
void addAtHead(int val) {
DList *newNode = new DList(val);
DList *next = sentinelNode->next;
newNode->prev = sentinelNode;
newNode->next = next;
size++;
sentinelNode->next = newNode;
next->prev = newNode;
}
void addAtTail(int val) {
DList *newNode = new DList(val);
DList *prev = sentinelNode->prev;
newNode->next = sentinelNode;
newNode->prev = prev;
size++;
sentinelNode->prev = newNode;
prev->next = newNode;
}
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index <= 0) {
addAtHead(val);
return;
}
int num;
int mid = size >> 1;
DList *curNode = sentinelNode;
if (index < mid) {
for (int i = 0; i < index; i++) {
curNode = curNode->next;
}
DList *temp = curNode->next;
DList *newNode = new DList(val);
curNode->next = newNode;
temp->prev = newNode;
newNode->next = temp;
newNode->prev = curNode;
} else {
for (int i = 0; i < size - index; i++) {
curNode = curNode->prev;
}
DList *temp = curNode->prev;
DList *newNode = new DList(val);
curNode->prev = newNode;
temp->next = newNode;
newNode->prev = temp;
newNode->next = curNode;
}
size++;
}
void deleteAtIndex(int index) {
if (index > (size - 1) || index < 0) {
return;
}
int num;
int mid = size >> 1;
DList *curNode = sentinelNode;
if (index < mid) {
for (int i = 0; i < index; i++) {
curNode = curNode->next;
}
DList *next = curNode->next->next;
curNode->next = next;
next->prev = curNode;
} else {
for (int i = 0; i < size - index - 1; i++) {
curNode = curNode->prev;
}
DList *prev = curNode->prev->prev;
curNode->prev = prev;
prev->next = curNode;
}
size--;
}
private:
int size;
DList *sentinelNode;
};
|
微信
