[LeetCode] 234. Palindrome Linked List

말하는 감자·2024년 12월 2일
algorithmdata structureleetcodelinked listpalindromepythontwo pointer리트코드알고리즘연결 리스트자료구조코딩테스트코딩테스트 준비투 포인터파이썬펠린드롬
1

LeetCode

목록 보기
19/32
post-thumbnail

이번 문제는 주어진 링크드 리스트가 펠린드롬인지를 판단하는 문제입니다. 살펴보겠습니다.

1. 오늘의 학습 키워드

  • Palindrome
  • Linked List
  • Stack
  • Two Pointer

2. 문제: 234. Palindrome Linked List

Description

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is in the range [1, 105].
  • 0 <= Node.val <= 9

Follow up:

Could you do it in O(n) time and O(1) space?

3. 문제 풀이

Step1. 문제 이해하기

주어진 연결 리스트가 펠린드롬인지를 판별하는 문제입니다.

  • Input:
    • 주어진 연결리스트의 길이는 1이상 10510^5이하입니다.
      • 빈 리스트는 들어오지 않는다는 것을 의미하고 시간 복잡도는 O(n2)O(n^2)보다 효율적이어야 합니다.
    • 노드의 값은 0이상 9이하입니다.
  • Output:
    • 펠린드롬이면 True, 그렇지 않으면 False를 반환합니다.

Follow up에서 시간 복잡도 O(n), 공간 복잡도 O(1)이 가능하냐고 묻습니다. 이는 값을 저장하는 자료구조를 활용하지 않고 구현이 가능한 지를 묻는것입니다.

즉, 연결 리스트를 순회하면서 지점의 위치를 변경하는 Two Pointer를 사용한다면 공간 복잡도 O(1)이 가능할 것으로 보입니다.

Step2. 문제 분석하기

주어진 문제는 연결 리스트의 노드를 순회하면서 펠린드롬인지를 확인해야 합니다.

가장 떠오른 방법은 연결 리스트의 노드 값을 빈 리스트에 저장합니다. 저장된 리스트의 값과 이것을 뒤집은 값이 같은지, 다른지를 판별하면 문제가 해결될 것으로 보입니다. 이 방법은 스택을 통해서도 비교가 가능합니다.

하지만, 해당 방법은 공간 복잡도가 O(n)이 나옵니다. 앞 서 말했듯이, 투 포인터를 활용한다면 조금 더 효율적으로 구성될 것 같습니다.

한 칸씩 이동하는 포인터와 두 칸씩 이동하는 포인터를 초기화 합니다. 그 다음 연결 리스트의 중간 까지 온다음 중간부터의 노드들의 next방향을 바꿉니다. 즉, 연결 리스트의 절반을 뒤집는 과정을 거칩니다(이전에 제가 올린 문제의 방법을 사용하면 됩니다.) 마지막으로 두 연결 리스트의 값을 비교하면 해결됩니다.

노드를 순회하기 때문에 재귀방법도 가능할 것으로 보입니다.

이렇게 문제에 대한 다양한 접근 방법을 구성 완료했습니다.

코드 설계를 해보도록 하겠습니다.

Step3. 코드 설계

이 문제는 다양한 접근 방법을 활용할 수 있으며, 각각의 장단점과 효율성을 고려해 설계합니다.

  1. Linked List 값을 리스트에 저장하여 확인:
    • 연결 리스트의 값을 배열에 저장한 후, 배열이 펠린드롬인지 확인합니다.
    • 간단한 구현이 가능하지만, 추가 메모리 사용(O(n)O(n))이 필요합니다.
  2. Two Pointer를 사용해 연결 리스트의 절반을 뒤집고 비교:
    • 연결 리스트의 중간까지 탐색한 후, 후반부를 뒤집어 앞부분과 비교합니다.
    • 추가 공간 없이(공간 복잡도 O(1)O(1)) 효율적으로 구현 가능합니다.
  3. 스택을 사용하여 확인:
    • 연결 리스트의 값을 스택에 저장한 후, 원래 연결 리스트와 비교합니다.
    • O(n)O(n)의 추가 공간이 필요하지만 직관적인 접근 방식입니다.
  4. 재귀를 사용하여 뒤에서부터 확인:
    • 재귀 호출로 연결 리스트를 뒤에서부터 확인하며 펠린드롬 여부를 판단합니다.
    • 공간 복잡도는 호출 스택 때문에 O(n)O(n)입니다.

Step4. 코드 구현

Linked List

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    # 1. Linked List
    def isPalindrome(self, head):
        # https://leetcode.com/problems/palindrome-linked-list/submissions/1467936746
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        a = []
        curr = head
        while curr:
            a.append(curr.val)
            curr = curr.next
        
        if a != list(reversed(a)):
            return False
        return True
  • 코드 설명:
    1. 연결 리스트의 값을 a라는 리스트에 저장합니다.
    2. 저장된 리스트와 역순으로 정렬된 리스트를 비교해 펠린드롬 여부를 판단합니다.
  • 시간 복잡도: O(n)O(n) – 연결 리스트의 순회와 리스트 비교.
  • 공간 복잡도: O(n)O(n) – 리스트 a를 저장하기 위한 공간.
  • 결과: https://leetcode.com/problems/palindrome-linked-list/submissions/1467936746

Two Pointer

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# # 2. Two Pointer
    def isPalindrome(self, head):
        # https://leetcode.com/problems/palindrome-linked-list/submissions/1467944691
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        slow, fast = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node
        
        l, r = head, prev
        while r:
            if l.val != r.val:
                return False
            l = l.next
            r = r.next
        return True
  • 코드 설명:
    1. fast와 slow 포인터를 사용해 중간 지점을 찾습니다.
    2. slow부터 끝까지 연결 리스트를 뒤집습니다.
    3. 원래의 앞부분과 뒤집힌 뒷부분을 비교하며 펠린드롬 여부를 판단합니다.
  • 시간 복잡도: O(n)O(n) – 리스트 순회 및 비교.
  • 공간 복잡도: O(1)O(1) – 추가 공간 없이 포인터만 사용.
  • 결과: https://leetcode.com/problems/palindrome-linked-list/submissions/1467944691

Stack

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# 3. Stack
    def isPalindrome(self, head):
        # https://leetcode.com/problems/palindrome-linked-list/submissions/1467948467
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        stack = []
        curr = head

        while curr:
            stack.append(curr.val)
            curr = curr.next
        
        curr = head
        while curr:
            if curr.val != stack.pop():
                return False
            curr = curr.next
        return True

재귀 방법

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# 4. Recursion
    def isPalindrome(self, head):
        # https://leetcode.com/problems/palindrome-linked-list/submissions/1467954119
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        self.pointer = head
        def recursive_check(node):
            
            # base case
            if not node:
                return True

            if not recursive_check(node.next):
                return False
            
            if node.val != self.pointer.val:
                return False
            
            self.pointer = self.pointer.next
            return True

        return recursive_check(head)
  • 코드 설명:
    1. 재귀 호출로 리스트를 순회하며 뒤에서부터 값을 확인합니다.
    2. 연결 리스트의 첫 번째 노드를 시작점으로 사용해 값을 비교합니다.
  • 시간 복잡도: O(n)O(n) – 리스트 순회.
  • 공간 복잡도: O(n)O(n) – 재귀 호출 스택 사용.
  • 결과: https://leetcode.com/problems/palindrome-linked-list/submissions/1467954119

4. 마무리

이번 문제는 펠린드롬을 확인하는 알고리즘을 다양한 방식으로 구현해보며 연결 리스트의 다양한 접근 방법을 배울 수 있었습니다. 특히, Two Pointer 방식을 활용하면 O(n) 시간과 O(1) 공간 복잡도로 효율적으로 해결할 수 있음을 알 수 있었습니다.

연결 리스트와 펠린드롬 문제는 실전에서도 자주 등장하는 문제입니다. 이번 기회를 통해 다양한 구현 방법과 효율성을 익혀두시면 도움이 될 것입니다.

테스트 케이스를 전부 실행하는 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다.

profile
말하는 감자
할 수 있다
이전 포스트

[LeetCode] 206. Reverse Linked List

다음 포스트

[LeetCode] 83. Remove Duplicates from Sorted List

0개의 댓글