Remove Linked List Elements

Problem

• Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Approach

• 1. Create a dummy node whose next value is the head
• 2. Iterate through the list with the head (curr) and set its next value to next.next or nil depending on the value of next
• 3. Return next.next

Go Solution

func removeElements(head *ListNode, val int) *ListNode {
	dummy := &ListNode{Val: 0, Next: head}
	curr := dummy

	if curr == nil {
		return nil
	}

	for curr != nil {
		for curr.Next != nil && curr.Next.Val == val {
			if curr.Next != nil {
				curr.Next = curr.Next.Next
			} else {
				curr.Next = nil
			}
		}
        curr = curr.Next
	}

	return dummy.Next
}

Performance

• Runtime beats: 100%
• Memory beats: 80%

Complexity

• Time: O(n)
• Space: O(n)