isListPalindrome

주어진 정수로 구성된 단일 연결 리스트가 회문인지 확인하는 두 가지 일반적인 접근 방식이 있습니다.

1. 스택 사용:
   • 연결 리스트를 순회하고 값을 스택에 넣습니다.
   • 그런 다음 리스트를 다시 순회하고 스택에서 꺼낸 값을 현재 노드와 비교합니다.
   • 모든 노드가 일치하면 연결 리스트는 회문입니다.
   • 그렇지 않으면 회문이 아닙니다.
   • 이 접근 방식은 O(n) 시간 복잡도를 가지며 스택에 추가 공간을 사용합니다.
2. 두 번째 절반 뒤집기:
   • 연결 리스트의 중간 지점을 찾습니다.
   • 두 번째 절반을 뒤집습니다.
   • 첫 번째 절반과 뒤집힌 두 번째 절반을 비교합니다.
   • 일치하면 연결 리스트는 회문입니다.
   • 그렇지 않으면 회문이 아닙니다.
   • 이 접근 방식도 O(n) 시간 복잡도를 가지지만 추가 공간은 **O(1)**만 사용합니다.

문제에서 시간 복잡도 o(n), 공간 복잡도 O(1)로 해결하라고 하였기 때문에,

2번째 방법을 사용하여야 합니다,

// Singly-linked lists are already defined with this interface:
// class ListNode<T> {
//   public T value { get; set; }
//   public ListNode<T> next { get; set; }
// }

bool solution(ListNode<int> l) {
    ListNode<int> slow = l;
    ListNode<int> fast = l;
    
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
     ListNode<int> secondHalf = ReverseList(slow);
    
    while(secondHalf != null){
        if(l.value != secondHalf.value){
            return false;
        }
        l = l.next;
        secondHalf = secondHalf.next;
    }
    return true;
}

ListNode<int> ReverseList(ListNode<int> head){
    ListNode<int> prev = null;
    ListNode<int> curr = head;
    
    while(curr != null){
        ListNode<int> nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}