Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
移除所有和给定值相等的链表元素。
解法1：迭代
解法2: 递归
Java:
/**
* 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) {
if (head == null) return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
Java:
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
if(head.val == val) return removeElements(head.next, val);
ListNode preMark = head, nextMark = head;
while(nextMark.next != null && nextMark.next.val != val){
nextMark = nextMark.next;
}
// This line could be deleted, i kept it here for a full logic cycle.
if(nextMark.next == null) return head;
preMark = nextMark;
nextMark = nextMark.next;
preMark.next = removeElements(nextMark, val);
return head;
}
Python:
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if not head:
return None head.next = self.removeElements(head.next, val) return head.next if head.val == val else head
Python: wo from G
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
while head and head.val == val:
head = head.next if head:
head.next = self.removeElements(head.next, val) return head
Python:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
# @param {ListNode} head
# @param {integer} val
# @return {ListNode}
def removeElements(self, head, val):
dummy = ListNode(float("-inf"))
dummy.next = head
prev, curr = dummy, dummy.next while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr curr = curr.next return dummy.next
Python:
def removeElements(self, head, val):
dummy = ListNode(-1)
dummy.next = head
pointer = dummy while(pointer.next): if pointer.next.val == val:
pointer.next = pointer.next.next
else:
pointer = pointer.next return dummy.next
C++: Iterration
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummy = new ListNode(-1), *pre = dummy;
dummy->next = head;
while (pre->next) {
if (pre->next->val == val) {
ListNode *t = pre->next;
pre->next = t->next;
t->next = NULL;
delete t;
} else {
pre = pre->next;
}
}
return dummy->next;
}
};
C++: Recursion
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head) return NULL;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};