题目1描述：
1
2
3
4
5
6
7
8
9
| 给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点
链表节点与函数的定义如下：
struct ListNode {
int m_nValue;
ListNode* m_pNext;
};
void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted);
|
解法1：
在单向链表中删除一个节点，常规的做法是从链表的头节点开始，顺序遍历查找要删除的节点，并在链表中删除该节点，这种思路由于需要顺序查找，时间复杂度自然就是O(n)了；之所以需要从头开始查找，是因为我们需要得到将被删除的节点的前一个节点。在单向链表中，节点中没有指向前一个节点的指针，所以只好从链表的头节点开始顺序查找
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
|
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted) {
if(pListHead == NULL || pToBeDeleted == NULL) return;
if(pToBeDeleted->m_pNext != NULL) {
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext;
delete pNext;
pNext = NULL;
}
else if(*pListHead == pToBeDeleted) {
delete pToBeDeleted;
pToBeDeleted = NULL;
*pListHead = NULL;
}
else {
ListNode* pNode = *pListHead;
while(pNode->m_pNext != pToBeDeleted) {
pNode = pNode->m_pNext;
}
pNode->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
|
⭐️值得注意的是，上述代码仍然不是完美的代码，因为它基于一个假设：要删除的节点的确在链表中，我们需要O(n)的时间才能判断链表中是否包含某一节点。受到O(1)时间的限制，我们不得不把确保节点在链表中的责任推给了函数DeleteNode的调用者。在面试的时候，我们可以和面试官讨论这个假设。
❗️LeetCode_83_删除排序链表中的重复元素
题目2_1描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次。返回同样按升序排列的结果链表。
示例：
输入：head = [1,1,2]
输出：[1,2]
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
1. 链表中节点数目在范围 [0, 300] 内
2. -100 <= Node.val <= 100
3. 题目数据保证链表已经按升序排列
|
解法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
25
26
27
28
29
30
|
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return NULL;
ListNode* cur = head;
while (cur->next != NULL) {
if (cur->val == cur->next->val) {
cur->next = cur->next->next;
}
else {
cur = cur->next;
}
}
return head;
}
};
|
❗️LeetCode_82_删除排序链表中的重复元素2
题目2_2描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。
示例：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
1. 链表中节点数目在范围 [0, 300] 内
2. -100 <= Node.val <= 100
3. 题目数据保证链表已经按升序排列
|
解法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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return NULL;
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
while (cur->next != NULL && cur->next->next != NULL) {
if (cur->next->val == cur->next->next->val) {
int x = cur->next->val;
while (cur->next != NULL && cur->next->val == x) {
cur->next = cur->next->next;
}
}
else {
cur = cur->next;
}
}
return dummy->next;
}
};
|
❗️LeetCode_237_删除链表中的节点
题目3_1描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
示例1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
1.题目保证链表中节点的值互不相同
2.若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
|
解法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
25
26
27
28
|
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if (head -> val == val) return head -> next;
ListNode *pre = head, *cur = head -> next;
while(cur != NULL && cur -> val != val) {
pre = cur;
cur = cur->next;
}
if(cur != NULL) pre -> next = cur -> next;
return head;
}
};
|
解法2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
void deleteNode(ListNode* node) {
node -> val = node -> next -> val;
node -> next = node -> next -> next;
}
};
|
❗️LeetCode_203_移除链表元素
题目3_2描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
示例：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
输入：head = [], val = 1
输出：[]
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
1. 列表中的节点数目在范围 [0, 10^4] 内
2. 1 <= Node.val <= 50
3. 0 <= val <= 50
|
解法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
25
26
27
28
29
30
31
|
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (head == NULL) return NULL;
ListNode* dummyHead = new ListNode(0, head);
ListNode* temp = dummyHead;
while (temp->next != NULL) {
if (temp->next->val == val) {
temp->next = temp->next->next;
} else {
temp = temp->next;
}
}
return dummyHead->next;
}
};
|
❗️LeetCode_19_删除链表的倒数第N个节点
题目4描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例:
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
输入：head = [1], n = 1
输出：[]
输入：head = [1,2], n = 1
输出：[1]
输入：head = [1,2], n = 2
输出：[2]
提示：
1. 链表中结点的数目为 sz
2. 1 <= sz <= 30
3. 0 <= Node.val <= 100
4. 1 <= n <= sz
|
解法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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class Solution {
public:
int getLength(ListNode* head) {
int length = 0;
while (head != NULL) {
++length;
head = head->next;
}
return length;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = head;
int length = getLength(head);
if (length < n || length == 0) return NULL;
else if (length == 1 && n == 1) return NULL;
else if (length == n) return dummy->next;
ListNode* cur = dummy;
for (int i = 1; i < length - n; ++i) {
cur = cur->next;
}
cur->next = cur->next->next;
return dummy;
}
};
|
