[리트코드] Palindrome Linked List(python)

리트코드, Palindrome Linked List_연결리스트 팰린드롬

 

TL;DR

• 연결 리스트(Linked List)를 활용하여 팰린드롬 문제를 해결할 수 있는지

문제 분석

1. 주어진 연결 리스트 head가 팰린드롬일 경우 true를 반환하여라.

 

- 1 : 해결해야 하는 문제에 대해서 말하고 있다. 특이한 점은 연결 리스트로 자료형이 주어져 있다는 것이다.

입출력 형태

입출력 예시

 

- 예시에서는 리스트 형태로 입력이 주어지지만, 입력은 연결 리스트 형태로 주어진다.

class ListNode:
	def __init__(self, val=0, next=None):
    	self.val = val
        self.next = next

 

- val에는 해당하는 노드의 값이 주어지고, next에는 연결된 다음 연결 리스트가 주어진다.

- print문을 통해서 출력을 해보면 아래 그림과 같다.

입력으로 주어진 연결 리스트의 형태

 

- 이와 같이 주어진 연결 리스트가 팰린드롬 조건을 만족하면 True, 아니라면 False를 반환하면 된다.

풀이

- 문제는 다양한 방법으로 풀 수 있다.

- 리스트(list)와 데크(deque)를 사용하는 추가적인 메모리를 할당하는 방법과, 현재 공부하고 있는 책인 "파이썬 알고리즘 인터뷰"에서 소개하는 런너(Runner) 기법을 사용한, 추가적인 메모리 할당 없이 문제를 풀 수 있는 방법이 있다.

 

1. 리스트와 투 포인터를 활용한 방법

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
    	if not head:
            return True
            
        palindrome = []
        while head:
       	    palindrome.append(head.val)
            head = head.next
            
        # two pointer
        left, right = 0, len(palindrome) - 1
        while left < right:
            if palindrome[left] == palindrome[right]:
                left += 1
                right -= 1
            else:
                return False
            
        return True

 

- 만약, 주어진 연결 리스트 head가 비어 있다면 그 즉시 True를 반환하고 종료한다. 비어 있는 연결 리스트도 팰린드롬으로 볼 수 있다.

- 연결 리스트에 저장된 val을 저장할 리스트 palindrome를 선언한다.

- head가 None이 아닐 때까지, 저장된 val을 리스트에 저장한다. 저장한 이후에는 next를 통해 다음 노드로 넘어가야 한다.

- 투 포인터를 활용하여 양 끝을 비교, 팰린드롬인지 여부를 판단한다. 만약, palindrome[left]와 palindrome[right]가 다를 경우 팰린드롬이 아니므로 False를 반환한다.

- palidrome.pop(0)와 palindrome.pop()을 비교하는 방법으로도 문제를 해결할 수 있다.

 

2. deque를 사용하는 방법

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
    	if not head:
            return True
            
        palindrome: deque = deque()
        while head:
       	    palindrome.append(head.val)
            head = head.next
            
        while len(palindrome) > 1:
            if palindrome.popleft() != palindrome.pop():
            	return False
            
        return True

 

- 리스트 대신 데크를 사용한 풀이 방법이다.

- O(n)이 필요한 pop(0) 연산을 O(1)인 데크의 popleft() 메소드를 통해서 시간 복잡도에서 유리함을 얻을 수 있다.

 

3. 연결 리스트를 그대로 사용한 풀이

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True
        
        rev = None 
        slow, fast = head, head # 1
        
        while fast and fast.next: # 2
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next 
            
        if fast: # 3
            slow = slow.next
            
        while rev and rev.val == slow.val: # 4
            rev, slow = rev.next, slow.next
        return not rev

 

- 런너 기법은 서로 속도가 다른 두 개의 런너를 사용하여, 빠른 런너가 연결 리스트에 끝까지 갔을 때, 느린 런너가 연결 리스트의 중간 지점에 도착하도록 하여, 중간 지점을 중심으로 값을 비교하거나, 뒤집어야 할 때 유용하게 사용할 수 있다고 책에서 설명하고 있다.

- 1. slow와 fast는 처음에는 시작 지점인 head에서 시작한다.

- 2. fast가 연결 리스트의 끝까지 도착할 때까지 각 런너들이 이동한다.

    - fast는 두 번 이동, slow는 한 번 이동한다.

    - 이 때, slow의 val을 rev라는 연결 리스트에 저장한다. 이 rev는 주어진 연결 리스트의 역순으로, 중간 지점 이후의 값과 비교하기 위해 사용한다.

    - rev에는 slow를, rev.next는 아직 없으로므로 현재 rev를, slow는 다음 단계로 이동한 slow를 할당한다.

- 3. 연결 리스트의 길이가 홀수인 경우를 위한 처리이다. 중간 지점은 팰린드롬에 포함되지 않으므로 넘겨주어야 한다.

    - 이 과정이 지나면 rev는 2 -> 1 -> None 형태의 연결 리스트가 되고, slow는 중간 지점 이후의 연결 리스트들이 남게 된다.

- 4. 역순 연결 리스트인 rev와 남은 slow의 val을 비교한다. 

    - 팰린드롬일 경우에는 모든 연결 리스트를 조회하고 rev와 slow 모두 None이 된다. 따라서 이 때는 not rev 또는 not slow를 반환한다.

    - 팰린드롬이 아닐 경우에는, rev와 slow가 None이 아니기 때문에 False가 반환된다.

 

- 정리하자면 slow가 조회하는 값들을 연결 리스트에 배치함으로써, 중간 지점을 중심으로 왼쪽의 연결 리스트를 역순으로 배치하고, 이를 오른쪽 연결 리스트와 비교하는 것이 되겠다.