NUHMAN.com

Problem Statement

Given the head of a linked list and an integer val, remove all the nodes of the linked list that have val as their value.

Return the head of the modified linked list.

Function Signature:

go

func removeElements(head *ListNode, val int) *ListNode

Example 1:

go

head := &ListNode{1, &ListNode{2, &ListNode{6, &ListNode{3, &ListNode{4, &ListNode{5, &ListNode{6, nil}}}}}}}
val := 6
fmt.Println(removeElements(head, val)) 
// Output: [1, 2, 3, 4, 5]

Example 2:

go

head := &ListNode{7, &ListNode{7, &ListNode{7, nil}}}
val := 7
fmt.Println(removeElements(head, val)) 
// Output: nil

Constraints:

• The number of nodes in the list is in the range [0, 10^4].
• 1 <= Node.val <= 50
• 0 <= val <= 50

Approach

The problem can be solved with the following approach:

1. Iterate Through the List:

• We iterate through the linked list.
• For each node, if the value of the node is equal to val, we remove the node.
• This involves adjusting the pointers of the previous node to skip over the node that needs to be removed.

1. Handling Edge Cases:

• The list could be empty, in which case we return nil.
• The node to be removed might be at the head, so we need to ensure the head pointer is adjusted correctly.
• Consecutive nodes with the same value need to be removed as well.

1. Pointers:

• Use two pointers: current (to iterate through the list) and prev (to adjust the links).
• After removing a node, we need to make sure that the prev pointer points to the next valid node.

Steps:

1. Create a dummy node at the start of the list. This simplifies the handling of edge cases (like removing the head).
2. Traverse the list, checking each node's value.
3. If the node’s value matches val, adjust the prev pointer to skip the current node.
4. Finally, return the head of the modified linked list.

Time Complexity:

The time complexity is O(n) where n is the number of nodes in the linked list since we need to iterate through the list once.

Go Implementation

go

package main

import "fmt"

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// Function to remove all nodes with the given value
func removeElements(head *ListNode, val int) *ListNode {
    // Create a dummy node to handle edge cases (like removing head)
    dummy := &ListNode{Next: head}
    prev := dummy
    current := head

    // Traverse the list
    for current != nil {
        if current.Val == val {
            prev.Next = current.Next // Skip the current node
        } else {
            prev = current // Move prev to current node
        }
        current = current.Next // Move current to next node
    }

    return dummy.Next // Return the modified list (dummy.Next is the new head)
}

// Helper function to create a linked list from a slice
func createLinkedList(nums []int) *ListNode {
    dummy := &ListNode{}
    current := dummy
    for _, num := range nums {
        current.Next = &ListNode{Val: num}
        current = current.Next
    }
    return dummy.Next
}

// Helper function to print the linked list
func printLinkedList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " ")
        head = head.Next
    }
    fmt.Println()
}

func main() {
    // Example 1
    head := createLinkedList([]int{1, 2, 6, 3, 4, 5, 6})
    val := 6
    newHead := removeElements(head, val)
    printLinkedList(newHead) // Output: 1 2 3 4 5

    // Example 2
    head = createLinkedList([]int{7, 7, 7})
    val = 7
    newHead = removeElements(head, val)
    printLinkedList(newHead) // Output: (empty list)
}

Explanation of the Code:

1. ListNode Struct:

• This struct defines a node in the linked list. It has an integer value Val and a pointer Next to the next node in the list.

2. removeElements Function:

• Input: The function takes in the head of a linked list and a value val.
• Dummy Node: A dummy node is created before the actual head to simplify edge case handling.
• Traversal: We iterate through the list with the current pointer. The prev pointer tracks the previous node so we can modify its Next pointer when removing a node.
• Node Removal: If the current node's value matches val, we update prev.Next to skip the current node.
• Return: The function returns dummy.Next, which points to the new head of the list.

3. Helper Functions:

• createLinkedList(nums []int) creates a linked list from a slice of integers.
• printLinkedList(head *ListNode) prints the values of the linked list from head to tail.

4. Main Function:

• Two test cases are created and passed to the removeElements function.
• The results are printed using printLinkedList.

Example Walkthrough

Example 1:

Input:

go

head := &ListNode{1, &ListNode{2, &ListNode{6, &ListNode{3, &ListNode{4, &ListNode{5, &ListNode{6, nil}}}}}}}
val := 6

• Start with the list: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6.
• Remove nodes with value 6, resulting in: 1 -> 2 -> 3 -> 4 -> 5.

Output: 1 2 3 4 5

Example 2:

Input:

go

head := &ListNode{7, &ListNode{7, &ListNode{7, nil}}}
val := 7

• Start with the list: 7 -> 7 -> 7.
• All nodes have value 7, so the entire list is removed, resulting in an empty list.

Output: (empty list)

Conclusion

The LeetCode 203: Remove Linked List Elements problem can be solved efficiently by iterating through the list once and adjusting pointers as necessary. Using a dummy node simplifies the handling of edge cases like removing the head of the list.

This solution runs in O(n) time complexity, where n is the number of nodes in the linked list, which is optimal for this problem.