Question

Formatted question description: https://leetcode.ca/all/203.html

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

 Example:

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

 @tag-array

Algorithm

Note that you still need to add a dummy node at the beginning of the linked list.

Code

Java

  • 
    public class Remove_Linked_List_Elements {
        /**
         * Definition for singly-linked list.
         * public class ListNode {
         *     int val;
         *     ListNode next;
         *     ListNode(int x) { val = x; }
         * }
         */
    
        // time: O(N)
        // space: O(N)
        class Solution {
            public ListNode removeElements(ListNode head, int val) {
                if (head == null) {
                    return head;
                }
    
                ListNode dummy = new ListNode(0);
                dummy.next = head;
    
                ListNode prev = dummy;
                ListNode current = head;
    
                while (current != null) {
                    if (current.val == val) {
                        prev.next = current.next;
                        current = current.next;
                    } else {
                        prev = prev.next;
                        current = current.next;
                    }
                }
    
                return dummy.next;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/remove-linked-list-elements/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        ListNode* removeElements(ListNode* head, int val) {
            ListNode dummy, *tail = &dummy;
            while (head) {
                auto p = head;
                head = head->next;
                if (p->val == val) continue;
                tail->next = p;
                tail = p;
            }
            tail->next = NULL;
            return dummy.next;
        }
    };
    
  • # 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
        p = dummy
        while p.next:
          if p.next.val == val:
            p.next = p.next.next
          else:
            p = p.next
        return dummy.next
    
    

All Problems

All Solutions