LeetCode. Palindrome Linked List [Linked List]

Problem:

Given a singly linked list, determine if it is a palindrome.

 

Example 1:

Input: 1->2

Output: false

 

Example 2:

Input: 1->2->2->1

Output: true

 

-Summary-

1. Find a middle node using two-pointer in the original Linked list. (Fast and Slow)

2. Create a reverse_node and reverse the second half of the original Linked List

3. Compare 1st and 2nd half of the Linked list, if everything matches return True. Otherwise, return False.

 

이번문제는 reverse 부분에서 애를 많이 먹었다. discussion에서의 도움으로 이해할수 있었고 문제를 풀수 있었다.

만약 space를 extra로  쓸수 있다면 아래와 같이 간단하게 풀수 있다.

leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/772/discuss/64514/5-lines-Python-O(n)-time-and-space

def isPalindrome(self, head):
    vals = []
    while head:
        vals += head.val,
        head = head.next
    return vals == vals[::-1]

-Similar code-

# 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: ListNode) -> bool:
        #Using slow / fast runner 
        rev = None
        slow = fast = head
        
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next #Multiple assignment to avoid refernce issue
            
        if fast:
            slow = slow.next
        
        while rev and rev.val == slow.val:
            rev, slow = rev.next, slow.next
        
        return not rev

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]