[Python] LeetCode 234. Palindrome Linked List

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

Palindrome Linked List - LeetCode

링크드 리스트가 주어졌을 때, 값이 좌우대칭인 Palindrome인지 판별하는 문제.

사실 Deque를 쓰면 매우 간단한 문제다.

Deque까지 쓰지 않더라도, 리스트로 값을 저장할 수만 있다면 리스트 파싱으로도 쉽게 해결할 수 있다.

 

링크드 리스트의 특징을 살린 방법인 Runner를 적용해 보았다.

아래 코드는 이 책의 풀이를 참고하였다.

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기

 

	# Definition for singly-linked list.
	class ListNode:
	def __init__(self, val=0, next=None):
	self.val = val
	self.next = next
	from collections import deque
	class Solution:
	def isPalindrome(self, head: ListNode) -> bool:
	# Runner 활용한 풀이
	# 두칸씩 이동하는 fast, 한칸씩 이동하는 slow를 정의하면
	# fast가 끝까지 도착하면 slow는 절반의 위치에 도달한다.
	# slow로 지나온 노드를 역순으로 rev에 저장하고
	# 절반의 지점에서부터 slow가 끝까지 도달할 때까지
	# slow와 rev 값을 비교한다.
	rev = None
	slow = fast = head
	while fast and fast.next:
	fast = fast.next.next
	rev, rev.next, slow = slow, rev, slow.next
	# 만약 전체 노드 길이가 홀수라면, fast.next는 None인데 fast는 not None이다. 두 칸씩 건너뛰기 때문.
	if fast:
	slow = slow.next
	# slow와 rev 값 비교
	while rev and rev.val == slow.val:
	slow, rev = slow.next, rev.next
	# 끝까지 도착했으면 rev는 None일테니 not rev는 True.
	return not rev

view raw [Leetcode] palindrome linked list-runner.py hosted with ❤ by GitHub