코딩 테스트 대비: 회문 연결 리스트 문제 풀이 (C#)

안녕하세요, GameLabMaster입니다! 이번에는 코딩 테스트에서 자주 등장하는 링크드 리스트 문제 중 하나인 '회문 연결 리스트(Palindrome Linked List)'를 다뤄보겠습니다.

 

문제
주어진 연결 리스트가 회문(palindrome)인지 확인하는 함수를 작성해야 합니다.

예시:

• Input: 1->2
• Output: false
• Input: 1->2->2->1
• Output: true

풀이
이 문제를 해결하기 위한 한 가지의 접근 방법은 두 포인터를 이용하는 것입니다: 빠른 포인터와 느린 포인터를 두어, 빠른 포인터가 연결 리스트의 끝에 도달할 때까지 느린 포인터를 중간 지점까지 이동시킵니다. 그런 다음, 느린 포인터 위치부터 연결 리스트를 뒤집고, 처음부터 중간 지점까지의 연결 리스트와 뒤집은 연결 리스트를 비교하여 회문 여부를 판단합니다.

다음은 C#으로 작성한 '회문 연결 리스트' 문제의 풀이 코드입니다.

 

public class Solution {
    public bool IsPalindrome(ListNode head) {
        ListNode fast = head, slow = head;

        // Move slow to middle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse second half
        slow = Reverse(slow);

        // Compare first half and second half
        while (slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }

        return true;
    }

    public ListNode Reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

 

이런 방법으로 회문 연결 리스트 문제를 해결할 수 있습니다. 링크드 리스트 문제는 포인터를 잘 다루는 능력이 중요하므로, 이 문제를 통해 연습해 보시기 바랍니다.

 

다음 포스팅에서는 다른 링크드 리스트 문제들을 함께 살펴보도록 하겠습니다.