203. Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/

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

Thoughts

将linked list中与val值相同的结点删除。删除val可看做在dummy后插入非val的节点。

Code

# 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, cur = ListNode(), head
        add = dummy
        while cur:
            if cur.val != val:
                add.next = cur
                add = add.next
            cur = cur.next
        add.next = None
        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy_node(-1);
        auto dummy = &dummy_node, node = dummy;
        dummy->next = head;
        while (node != NULL && node->next != NULL) {
            if (node->next->val == val) {
                node->next = node->next->next;
            } else {
                node = node->next;
            }
        }
        return dummy->next;
    }
};

Analysis

Errors:

1. node = node.next;没写在else里

时间复杂度O(n), 空间复杂度O(1)