[LeetCode] 203. Remove Linked List Elements - 문제풀이

Description

주어진 LinkedList에서 val값과 일치하는 노드를 제거한 후 반환합니다.

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, 10^4].
• 1 <= Node.val <= 50
• 0 <= val <= 50

Solution 1. 재귀호출 (Recursion)

public ListNode removeElements(ListNode head, int val) {

    //1.Recursion
    if(head == null) return null;
    head.next = removeElements2(head.next,val);  //끝에서부터 시작.
    if(head.val == val){
        return head.next;
    }else{
        return head;
    }
}

재귀 호출을 이용한 방법입니다. 다음 노드에 대해서 재귀호출로 끝 노드부터 채워주되 노드의 값이 val과 같을 경우 현재 노드의 다음노드를 반환, 아닐경우 자신을 그대로 반환해줍니다.

Solution 2. 반복 ( Iteration)

public ListNode removeElements2(ListNode head, int val) {

    //2.Iteration
    ListNode dHead = new ListNode(0);
    dHead.next = head;
    ListNode cur = dHead;
    while( cur.next != null ){
        if(cur.next.val == val){
            cur.next = cur.next.next;
        }else{
            cur = cur.next;
        }
    }
    return dHead.next;
}

반복문과 포인터를 이용한 방법입니다. 더미노드를 헤드 앞에 두고 다음 노드가 제거 대상일 경우 다다음 노드를 붙여주고 아닐 경우 그대로 한 칸만 이동시켜 줍니다.

Reference

Remove Linked List Elements - LeetCode