Leetcode - 203. Remove Linked List Elements

문제

링크드 리스트에서 val값을 가진 노드를 모두 제거하라

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

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

해결

노드가 헤드인경우와 아닌경우를 구분해야함.

struct ListNode *removeElements(struct ListNode *head, int val){
    struct ListNode *node = head;
    struct ListNode *prev = NULL;
    
    while (node != NULL) {
        if (node ->val != val) {
            prev = node;
            node = node->next;
            continue;
        }
        if (node == head) {
            head = node->next;
            prev = node;
            node = node->next;
        } else {
            prev->next = node->next;
            node = node->next;
        }
    }    
    return head;
}

230805 풀이

c++ 더 심플한 iterative 해결방법

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *new_head = new ListNode;
        new_head->next = head;
        ListNode *node = new_head;

        while (node->next) {
            if (node->next->val == val)
                node->next = node->next->next;
            else
                node = node->next;
        }
        return new_head->next;
    }
}

Recursion

재귀호출을 이용해 놀랍도록 심플하게 풀기 (230805 작성)

기본적으로 head->next 에 재귀호출 결과를 저장.
그 뒤 head가 val과 같은 값이면 head를 next로 변경하고 head리턴

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head)
            return NULL;
        head->next = removeElements(head->next, val);
        if (head->val == val)
            head = head->next;
        return head;
    }
}

재귀 호출 풀어 읽기
리스트의 마지막 노드부터 완성되어 첫번째 노드까지 저장되는순서

[1,2,3,4,5] val = 4 (제거)

1->rec(2)
   2->rec(3)
      3->rec(4)
         4->rec(5) 
            5->rec(null)
            5->null
         4->5->null  (4 == val 이기에 4->next리턴)
         5->null
      3->5->null
   2->3->5->null
1->2->3->5->null