LeetCode #203 Remove Linked List Elements

Posted on | Post modified | In , , , , , , , , , ,

Problem

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

Example

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Solution 1

Method:

Time Complexity: O(n)

Space Complexity: 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
25
26
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        prev = dummy = ListNode(float('-inf'))
        current = dummy.next = head
        
        while current:
            if current.val != val:
                prev.next = current
                prev = prev.next
            current = current.next

        if prev.next and prev.next.val == val:
            prev.next = None
        
        return dummy.next

Solution 2

Method: Recursive

Time Complexity:

Space Complexity:

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

class Solution:
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if not head:
            return head

        head.next = self.removeElements(head.next, val)
        
        return head.next if head.val == val else head