Leetcode - 234. Palindrome Linked List

문제

주어진 singlely 링크드 리스트의 노드가 palindrome인지 확인하라.

Input: head = [1,2,2,1]
Output: true

https://leetcode.com/problems/palindrome-linked-list/

해결 O(N) / O(N)

일단 리스트의 배열값을 추가 배열에 저장하고 그 배열값이 palindrome인지 확인. O(N)이긴 한데 더 효율적인 방법이 있을것.
배열을 새로 추가했으니 공간복잡도는 O(N)

int arr[100001];
bool isPalindrome(struct ListNode* head) {
    struct ListNode *node = head;
    memset(arr, 0, 100001);
    int arrcnt = 0;
    
    for (; node != NULL; node = node->next)
        arr[arrcnt++] = node->val;
    for (int i = 0; i < (arrcnt / 2); i++) {
        if (arr[i] != arr[arrcnt - 1 - i])
            return false;
    }
    return true;
}

추가로 palindrome 확인을 위해, 배열값이 양끝부터 가운데로 오면서 같은지 비교하는 방법은 아래방식이 더 읽기 쉬운 코드인것같다.

while (left < right) {
    if (arr[left++] != arr[right++])
        return false;
}

해결 O(N) / O(1)

리스트의 중간노드를 얻어내서 절반을 reverse 시키고 하나씩 비교하는 방법. 추가 배열이 필요없어 공간복잡도는 O(1)이다.

• 중간노드를 구하는 방법은 풀이에서 천재적인 아이디어를 배웠는데, 노드를 순회할때 두칸씩 순회하는 노드를 추가로 두면 2/N번만 순회해서 중간노드를 구할 수 있다.

    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;

• reverse linked list
  지난번에 한번 풀어봤던건데, 다시 풀려니 살짝 오래걸림. 링크드리스트 기초 연산이니, 이 패턴 및 구조를 반복해서 잘 숙지 하자.

struct ListNode *reversed_list(struct ListNode *head)
{
    struct ListNode *node = head;
    struct ListNode *prev = NULL; // reverse하면, 첫번째 노드 next는 NULL을 가리켜야함
    struct ListNode *tmp = head;;
    for (;node != NULL; prev = node, node = tmp) {  // prev, node 한칸씩 우측으로
        tmp = node->next;     // next노드 포인터 미리 저장
        node->next = prev;    // next를 prev노드로 변경
    }
    return prev;  // prev를 리턴
}

• 전체 코드

struct ListNode *get_middle_node(struct ListNode *head)
{
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode *reversed_list(struct ListNode *head)
{
    // 1 -> 2 -> 3 -> 4
    // 1 <- 2 <- 3 <- 4
    struct ListNode *node = head, *prev = NULL, *tmp = head;;
    for (;node != NULL; prev = node, node = tmp) {
        tmp = node->next;
        node->next = prev;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    struct ListNode *node = head;
    struct ListNode *first_end = get_middle_node(head);
    struct ListNode *reversed_begin = reversed_list(first_end->next);

    while (reversed_begin != NULL) {
        if (node->val != reversed_begin->val)
            return false;
        node = node->next;
        reversed_begin = reversed_begin->next;
    }
    return true;
}

230909 다시 풀이

c++

class Solution {
public:
    ListNode *reverse(ListNode* head) {
        ListNode *prev = NULL;
        ListNode *next = NULL;
        ListNode *node = head;
        
        for (; node; node = next) {
            next = node->next;
            node->next = prev;
            prev = node;
        }
        return prev;
    }
    bool isPalindrome(ListNode* head) {
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *rev = NULL;
        
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        rev = reverse(slow->next);
        
        while (rev) {
            if (head->val != rev->val)
                return false;
            head = head->next;
            rev = rev->next;
        }
        return true;
    }
};