•
문제 설명 : 주어진 연결리스트가 회문인지 확인
•
풀이 방법
◦
주어진 연결리스트를 모두 순회한 후, 양쪽 데이터를 확인하며 회문인지 확인하였다.
•
시간복잡도 :
•
성공 코드
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
info = []
cursor = head
while cursor.next:
info.append(cursor.val)
cursor = cursor.next
info.append(cursor.val)
for i in range(len(info) // 2):
if info[i] != info[~i]:
return False
return True
Python
복사
•
성공 코드(공간복잡도 O(1) / 솔루션 코드)
내용을 찾아보니, 러너 기법을 활용하여 문제를 푼다고 한다.
2칸씩 이동하는 fast 와 1칸씩 이동하는 slow 를 통하여 연결리스트의 끝과 중간 위치를 얻을 수 있다.
중간 요소인 slow Node 이후 연결되는 요소를 기존 요소가 아닌 새로운 요소(역순으로 설정된 Node)으로 설정한다.
만약 회문이라면, slow → 새로운 요소 == head → slow 일 것이다.
역순 연결 리스트를 만드는 순서 (Reversing the second half 부분)
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
# Finding Midpoint
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev, curr = None, slow
# Reversing the second half
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Checking if it's palidrome?
while head and prev:
if head.val != prev.val:
return False
head = head.next
prev = prev.next
return True
Python
복사