[링크드리스트] LeetCode 234번 문제 학습

문제 설명

Palindrome Linked List는 단일 연결 리스트가 회문인지 확인하는 문제임. 회문이면 true, 아니면 false 리턴. 예를 들어, 1->2->2->1은 회문이라 true, 1->2->3은 false. 시간복잡도 O(n), 공간복잡도 O(1)로 푸는 게 이상적.

 

푼 과정

세 단계로 풀었음. 첫째, 빠른/느린 포인터(center, end)로 리스트 중간 찾음. end가 두 칸, center가 한 칸씩 가서 중간 노드(center) 구함. 둘째, center부터 끝까지 reverseList로 뒤집음. 셋째, 원래 리스트 헤드(left)와 뒤집힌 리스트(prev)부터 동시에 순회하면서 값 비교. 다르면 false, 끝까지 같으면 true. 빈 리스트나 노드 하나는 바로 true 처리. 로직 탄탄하고 정석대로 잘 갔음.

---

알고리즘 분석

빠른/느린 포인터로 중간 찾기 O(n/2), 리스트 뒤집기 O(n/2), 값 비교 O(n/2)라 총 시간 O(n). 공간은 포인터 몇 개만 써서 O(1). 스택 방식(공간 O(n)) 대신 뒤집기로 공간 최적화 잘 했음. 재귀나 추가 자료구조 없이 연결 리스트 조작으로 효율적.

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	for head != nil {
			next := head.Next
			head.Next = prev
			prev = head
			head = next
	}
	return prev
}

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	// 1. 가운데 노드를 구하기
	center, end := head, head
	for end != nil && end.Next != nil {
		center = center.Next
		end = end.Next.Next
	}
	 
	// 2. 가운데 노드를 기준으로 뒤집기
	prev := reverseList(center)

	// 3. 뒤집은 가운데 노드와, head 노드를 동시에 출발시켜 데이터가 같은 지 확인하기
	left, right := head, prev
	for right != nil {
		if left.Val != right.Val {
				return false
		}
		left = left.Next
		right = right.Next
	}

	return true
}