[재귀,반복문] LeetCode 203번 문제 학습

문제 설명

Remove Linked List Elements는 단일 연결 리스트(Singly Linked List)에서 특정 값(val)과 같은 노드를 모두 제거하고, 수정된 리스트를 리턴하는 문제임. 

• 리스트가 1 -> 2 -> 6 -> 3 -> 6, val = 6이면, 결과는 1 -> 2 -> 3.
• 리스트가 6 -> 6, val = 6이면, 결과는 빈 리스트(nil).
• 리스트가 비어 있으면(head = nil), 그냥 nil 리턴.

제약 조건

• 리스트 노드 수는 0 이상.
• 노드 값과 val은 정수(int).
• 연결 리스트는 ListNode 구조체로 주어짐: Val (값), Next (다음 노드 포인터).
• 시간복잡도 O(n), 공간복잡도 O(1)로 푸는 게 이상적.

문제를 푼 과정

재귀랑 반복 둘 다 섞어서 풀었음.

1. 기저 사례 (Base Case)
   • head == nil이면 빈 리스트니까 바로 head 리턴. 이건 아무 처리 안 해도 됨.
   • 이 조건으로 재귀 끝나는 경우 처리함.
2. 헤드 노드 처리 (재귀)
   • head.Val == val이면 현재 헤드 노드가 제거 대상.
   • return removeElements(head.Next, val)로 헤드 건너뛰고 다음 노드부터 재귀 호출.
   • 이 방식으로 리스트 맨 앞에 연속된 val 값들 다 제거함.
3. 리스트 순회 (반복)
   • 헤드 노드가 제거 대상 아니면, 리스트를 순회하면서 나머지 노드 처리.
   • 두 포인터 사용:
     • prev: 현재 노드의 이전 노드.
     • cur: 현재 검사 중인 노드.
   • cur != nil 동안 반복:
     • cur.Val == val이면, prev.Next = cur.Next로 현재 노드 제거.
     • 아니면, prev = cur로 이전 노드 갱신.
     • cur = cur.Next로 다음 노드 이동.
   • 이 방식으로 중간이나 끝에 있는 val 노드들 제거함.

---

어떤 알고리즘 썼는지

연결 리스트 조작

1. 재귀 (Recursion)
   • 헤드 노드가 val과 같을 때 재귀로 다음 노드 처리.
   • 연속된 제거 대상 노드들 건너뛰는 데 유용.
   • 재귀 깊이는 제거 대상 노드 수에 비례. 최악의 경우 O(n).
2. 투 포인터 (Two Pointers)
   • prev와 cur 포인터로 리스트 순회.
   • prev는 연결 유지, cur는 제거 여부 판단.
   • 리스트 조작할 때 필수적인 패턴. 시간복잡도 O(n).
3. 연결 리스트 조작
   • 노드 제거는 prev.Next 갱신으로 O(1) 시간 걸림.
   • 전체 리스트 한 번 순회하니까 총 O(n).

package main

type ListNode struct {
    Val int
    Next *ListNode
}

func removeElements(head *ListNode, val int) *ListNode {
	if head == nil {
		return head
	}

	if head.Val == val {
		return removeElements(head.Next, val)
	}

	prev := head
	cur := head.Next

	for cur != nil {
		if cur.Val == val {
			prev.Next = cur.Next
		} else {
			prev = cur
		}
		cur = cur.Next
	}
	return head
}

func removeElements_v2(head *ListNode, val int) *ListNode {
	if head == nil {
		return head
	}

	if head.Val == val {
		return removeElements_v2(head.Next, val)
	}

	head.Next = removeElements_v2(head.Next, val)
	return head
}

func main() {
}