Welcome to Subscribe On Youtube

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

  • 
    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;
            }
        }
    }
    
    ############
    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            ListNode dummy = new ListNode(-1, head);
            ListNode pre = dummy;
            while (pre.next != null) {
                if (pre.next.val != val)
                    pre = pre.next;
                else
                    pre.next = pre.next.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:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def removeElements(self, head: ListNode, val: int) -> ListNode:
            dummy = ListNode(-1, head)
            pre = dummy
            while pre.next:
                if pre.next.val != val:
                    pre = pre.next
                else:
                    pre.next = pre.next.next
            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
    
    
  • func removeElements(head *ListNode, val int) *ListNode {
    	dummy := new(ListNode)
    	dummy.Next = head
    	p := dummy
    	for p.Next != nil {
    		if p.Next.Val == val {
    			p.Next = p.Next.Next
    		} else {
    			p = p.Next
    		}
    	}
    	return dummy.Next
    }
    
    
  • /**
     * Definition for singly-linked list.
     * class ListNode {
     *     val: number
     *     next: ListNode | null
     *     constructor(val?: number, next?: ListNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.next = (next===undefined ? null : next)
     *     }
     * }
     */
    
    function removeElements(head: ListNode | null, val: number): ListNode | null {
        const dummy: ListNode = new ListNode(0, head);
        let cur: ListNode = dummy;
        while (cur.next != null) {
            if (cur.next.val === val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
    
    
  • public class Solution {
        public ListNode RemoveElements(ListNode head, int val) {
            ListNode newHead = null;
            ListNode newTail = null;
            var current = head;
            while (current != null)
            {
                if (current.val != val)
                {
                    if (newHead == null)
                    {
                        newHead = newTail = current;
                    }
                    else
                    {
                        newTail.next = current;
                        newTail = current;
                    }
                }
                current = current.next;
            }
            if (newTail != null) newTail.next = null;
            return newHead;
        }
    }
    
  • // Definition for singly-linked list.
    // #[derive(PartialEq, Eq, Clone, Debug)]
    // pub struct ListNode {
    //   pub val: i32,
    //   pub next: Option<Box<ListNode>>
    // }
    //
    // impl ListNode {
    //   #[inline]
    //   fn new(val: i32) -> Self {
    //     ListNode {
    //       next: None,
    //       val
    //     }
    //   }
    // }
    impl Solution {
        pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
            let mut dummy = Box::new(ListNode { val: 0, next: head });
            let mut cur = &mut dummy;
            while let Some(mut node) = cur.next.take() {
                if node.val == val {
                    cur.next = node.next.take();
                } else {
                    cur.next = Some(node);
                    cur = cur.next.as_mut().unwrap();
                }
            }
            dummy.next.take()
        }
    }
    
    

All Problems

All Solutions