Remove Linked List Elements[E,Linked List,Recursion]

https://leetcode.com/problems/remove-linked-list-elements/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.

 

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

 

Constraints:

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

Linked list니까 이번엔 C++부터

 

1. C++

틀릴때마다 test case를 보면서 디버깅할 수 있으니까 편하다.

실전에선 이런 일이 잘 없지만..

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return nullptr;
        while(head and head->val == val){
            head = head->next;
        }
        ListNode* prev = head;
        ListNode* curr = head;
        while(curr){
            if(curr->val == val){
                prev->next = curr->next;
                curr = curr->next;
                continue;
            }
            prev = curr;
            curr = curr->next;
        }
        return head;
    }
};

 

2. C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    if(!head) return NULL;

    struct ListNode* new_ptr = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* prev = new_ptr;
    struct ListNode* temp = head;
    
    while(temp){
        if(temp->val != val){
            prev -> next = temp;
            prev = prev -> next;
        }else{
            prev->next = NULL;
        }
        temp = temp->next;
    }

    return new_ptr->next;
}

 

3. Python

# 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: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head : return None
        curr = head
        ans = ListNode()
        temp = ans
        while curr :
            if curr.val != val:
                temp.next = curr
                temp = temp.next
            else :
                temp.next = None
            curr = curr.next
        return ans.next

 

담백~하게 풀었다.