링크드리스트 기본문제, 팰린드롬은 리트코드 125 문자열 문제에서 설명
input 설명 (주의)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
걍 하나씩 꺼내서 리스트에 따로 저장해두지 모
그 이후는 리트코드 125랑 똑같이
내가 푼 방법으로도 풀이가 있고
런너(runner)를 이용한 풀이가 있음
그리고, reversn은 새로운 링크드 리스트임 (slow의 역순 링크드리스트)
따라서 slow가 중간지점부터 한칸씩 이동하고
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
arr = []
while 1:
arr.append(head.val)
if head.next == None: break # while조건으로 두면 마지막 노드는 무시되어버림
head = head.next
if arr == arr[::-1]: # 리스트 vs 리스트역순이 같으면 true
return True
else:
return False
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
reversn = None
slow = fast = head
while fast and fast.next:
# fast는 두 칸 이동
fast = fast.next.next
# 리버스 링크드리스트 생성과 동시에 slow는 한 칸 이동 (동시할당해야 같은 값을 참조안함 주의-딥카피같은)
reversn, reversn.next, slow = slow, reversn, slow.next
# 링크드리스트의 길이가 홀수인 경우 주의(slow를 한칸 더 이동해서 중앙 맞춰줌)
if fast:
slow = slow.next
# 팰린드롬 여부 확인
while reversn and reversn.val == slow.val:
slow, reversn = slow.next, reversn.next # 한칸씩 이동
return not reversn