[알고리즘][연결 리스트] - 1. 팰린드롬 연결리스트

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/palindrome-linked-list/submissions/

연결 리스트가 팰린드롬 구조인지 판별하라

---

[리스트 변환]

# 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:
        q : List = []
        
        if not head:
            return True
        node = head
        
        while node is not None:
            q.append(node.val)
            node = node.next
            
        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False
        return True

• 연결 리스트를 파이썬의 리스트로 변환하고 풀이를 진행했다.
• 이때 연결리스트를 리스트로 변환하지 않고 쓰는 것이 코드가 더욱 깔끔할 것 같다. 

 

 

[데크를 사용한 최적화]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import collections


class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        q : Deque = collections.deque()
        # q = deque()
        
        if not head:
            return True
        node = head

        while node is not None:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.popleft()!=q.pop():
                return False
        return True

# 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: Optional[ListNode]) -> bool:

        q = deque()

        if not head:
            return True
        node = head

        while node is not None:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.popleft()!=q.pop():
                return False
        return True

• 데크를 사용하면 요소를 앞에서 꺼내오고 앞에서 넣어주고 할 때 아주 빠르게 진행할 수 있어서 위에서 pop(0)보다 popleft( )를 사용할 때가 훨씬 빠르게 진행가능하다.

 

 

[러너(Runner) 기법을 사용한 풀이]

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        slow = fast = head
        
        #런너를 이용해 역순 연결 리스트 구성
        while fast and fast.next:
            fast = fast.next.next #두칸씩 구성
            rev, rev.next, slow = slow, rev, slow.next
            
        if fast:
            slow = slow.next
        
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev

• 데크로 구현한 풀이와 성능이 비슷하다.. (나라면 데크로 구현할 것 같다..)

 

 

[러너 기법이란?]

연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다.