leetcode203.Remove Linked List Elements

Problem Description

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

The key to solving this problem is to remove the nodes with a specified value from the linked list. We can achieve this by traversing the linked list and checking each node’s value. If the value matches the given val, we simply delete that node.

To simplify the process, we introduce a dummy head node called dummyHead and point it to the original head of the linked list. This allows us to perform operations directly on dummyHead.next without the need to handle the special case of the head node separately.

Next, we create a pointer cur to traverse the linked list. Starting from the dummy head node, we check if the value of the next node is equal to val.

If the value of the next node is equal to val, we update the next pointer of the current node to skip the next node, effectively deleting it.

If the value of the next node is not equal to val, we move the current node to the next node.

Finally, we return dummyHead.next as the new head of the modified linked list.

Implementation

public ListNode removeElements(ListNode head, int val) {
    // Create a dummy head node and point it to the original head
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    
    // Create a pointer for traversing the linked list
    ListNode cur = dummyHead;

    // Traverse the linked list and check if the next node's value is equal to the given value
    while (cur.next != null) {
        if (cur.next.val == val) {
            // If the value of the next node matches the given value, update the current node's next pointer to skip the next node
            cur.next = cur.next.next;
        } else {
            // If the value of the next node does not match the given value, move the current node to the next node
            cur = cur.next;
        }
    }
    
    // Return dummy head's next node as the new head of the modified linked list
    return dummyHead.next;
}

Complexity Analysis

• Time complexity: O(n), where n is the length of the linked list. We need to traverse the entire linked list once.
• Space complexity: O(1), using only constant extra space.

By introducing a dummy head node and using a pointer for traversal and deletion, we can efficiently remove nodes from the linked list with a linear time complexity. Additionally, since we are using only a constant amount of extra space, the space complexity is low.

This problem demonstrates a typical linked list operation. By understanding the characteristics of linked lists and applying auxiliary nodes and pointers effectively, we can efficiently solve similar problems.

感谢您的来访，获取更多精彩文章请收藏本站。