[Python] Linked List (1)

 

# typing hint 입력을 위한 라이브러리 호출
import typing

 

---

Problem 13. Palindrome Linked List

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

---

실행시간 비교

 

풀이	방식	Big-O	실행시간 순위
1	리스트 변환	O(n)	2위
2	데크를 이용한 최적화	O(n)	1위

---

Solution 1. 리스트 변환

 

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

 

 

def isPalindrome_1(head: 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(): # list의 .pop(0)은 O(n)임. O(1)이 되도록 개선이 필요
            return False
    return True

 

---

Solution 2. 데크를 이용한 최적화

import collections

 

def isPalindrome_1(head: ListNode) -> bool:
    q: Deque =collections.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

 

---

Solution 3: Leetcode 최다 득표 풀이 방식

def isPalindrome(head: ListNode) -> bool:
    # rev records the first half, need to set the same structure as fast, slow, hence later we have rev.next
    rev = None
    # initially slow and fast are the same, starting from head
    slow = fast = head
    while fast and fast.next:
        # fast traverses faster and moves to the end of the list if the length is odd
        fast = fast.next.next
        
        # take it as a tuple being assigned (rev, rev.next, slow) = (slow, rev, slow.next), hence the re-assignment of slow would not affect rev (rev = slow)
        rev, rev.next, slow = slow, rev, slow.next
    if fast:
       # fast is at the end, move slow one step further for comparison(cross middle one)
        slow = slow.next
    # compare the reversed first half with the second half
    while rev and rev.val == slow.val:
        slow = slow.next
        rev = rev.next
    
    # if equivalent then rev become None, return True; otherwise return False 
    return not rev

 

---

Problem 14. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

---

Solution 1. 재귀 구조로 연결

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    if (not l1) or (l2 and l1.val > l2.val):
        l1, l2 = l2, l1 # l1, l2를 비교해 작은 값이 왼쪽에 오도록 변수 스왑
    if l1:
        l1.next = self.mergeTwoLists(l1.next, l2) # next로 그 다음 값이 엮이도록 재귀 호출
    return l1

 

출처 : 파이썬알고리즘인터뷰