203. Remove Linked List Elements

  • 31.4%

https://leetcode.com/problems/remove-linked-list-elements/#/description

Remove all elements from a linked list of integers that have value val.

1
2
3
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

方法一:

前面设置一个哑变量

学习一下

1
2
ListNode *pseudo_head = new ListNode(0);
pseudo_head->next = head;

Concise C++ solution with pseudo ListHead

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *pseudo_head = new ListNode(0);
pseudo_head->next = head;
ListNode *cur = pseudo_head;
while(cur){
if(cur->next && cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
return pseudo_head->next;
}
};

我的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* prehead = new ListNode(0);
prehead->next = head;
ListNode* cur = prehead;
while(cur && cur->next){
ListNode* nex = cur->next;
while(nex!=NULL && nex->val==val)
nex = nex->next;
if(cur->next != nex)
cur->next = nex;
cur = nex;
}
return prehead->next;
}
};

https://discuss.leetcode.com/topic/19529/simple-and-elegant-solution-in-c

Simple and elegant solution in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode *removeElements(ListNode *head, int val)
{
ListNode **list = &head;

while (*list != nullptr)
{
if ((*list)->val == val)
{
*list = (*list)->next;
}
else
{
list = &(*list)->next;
}
}

return head;
}

Original recursive version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void removeHelper(ListNode *&head, int val)
{
if (head == nullptr)
{
return;
}
else if (head->val == val)
{
head = head->next;
}
else
{
removeHelper(head->next, val);
}
}

https://discuss.leetcode.com/topic/17550/concise-c-solution-with-pseudo-listhead

Concise C++ solution with pseudo ListHead

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *pseudo_head = new ListNode(0);
pseudo_head->next = head;
ListNode *cur = pseudo_head;
while(cur){
if(cur->next && cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
return pseudo_head->next;
}
};

2ms, 5.21%, October 15, 2016

https://discuss.leetcode.com/topic/12580/3-line-recursive-solution

1
2
3
4
5
6
7
public class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}

1ms, 48.64%, October 15, 2016

https://discuss.leetcode.com/topic/12725/ac-java-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode fakeHead = new ListNode(-1);
fakeHead.next = head;
ListNode curr = head, prev = fakeHead;
while(curr != null){
if(curr.val == val)
prev.next = curr.next;
else
prev = prev.next;
curr = curr.next;
}
return fakeHead.next;
}
}

python

116ms, 68.55%, October 15, 2016

https://discuss.leetcode.com/topic/12640/python-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
next = dummy

while next != None and next.next != None:
if next.next.val == val:
next.next = next.next.next
else:
next = next.next

return dummy.next
谢谢你,可爱的朋友。