203. Remove Linked List Elements
- Remove Linked List Elements:题目链接
基本思想：
- curNode: 当前节点 简称c
- nextNode:当前节点的下一个节点 简称n
之所以建虚拟的头结点：如果第一个元素就是要删除的元素，没有前驱节点要另外讨论，故用虚拟的头结点作为其前驱节点 ，统一操作
1
2
3
4
5
6
7
8
9
10
11
12
| 删除的元素 val = 6
dummyHead --> 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6
c n
c n
c n
c n
c n
c n
c==NULL
如果当前节点curNode的下一个节点nextNode的数据域和val相等 则将curNode指向nextNode的下一个节点,nextNode重新指向curNode的下一个节点，否则将curNode往后移，nextNode往后移
|
方法1：带头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // 时间复杂度O(N) 空间复杂度O(1)
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode ));
dummyHead->next = head;
struct ListNode *curNode = dummyHead;
while (curNode != NULL && curNode->next != NULL) {
struct ListNode *nextNode = curNode->next;
if (nextNode->val == val) {
curNode->next = nextNode->next;
free(nextNode);
} else {
curNode = curNode->next;
}
}
return dummyHead->next;
|
方法2：不带头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// 时间复杂度O(N) 空间复杂度O(1) 不带头结点
struct ListNode *removeElements(struct ListNode *head, int val) {
if (head==NULL){
return NULL;
}
while (head != NULL && head->val == val){ // 注意这里是while 比如 1 1 这种情况
head = head->next;
}
struct ListNode *curNode = head;
while (curNode != NULL && curNode->next != NULL) {
struct ListNode *nextNode = curNode->next;
if (nextNode->val == val) {
curNode->next = nextNode->next;
free(nextNode);
} else {
curNode = curNode->next;
}
}
return head;
}
|
方法3：递归求解
1
2
3
4
5
6
7
8
9
| // 时间复杂度O(N) 空间复杂度O(N) 递归求解
// 返回从head开始去除val的链表
struct ListNode *removeElements(struct ListNode *head, int val) {
if (NULL == head){ // 递归出口
return NULL;
}
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
|
pS: 源代码链接
