234-Palindrome Linked List

tags: Easy

Question

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

Key

  • linked list可以直接做true-false判斷
  • 如果直接用l1.next = l2,l1的後續節點會接上l2的所有節點
  • 想法:先找到總長度,計算一半的位置,使用兩個list儲存左右兩邊,再分別取出來比較

Solution

C++ sol.

bool isPalindrome(ListNode* head) { if(head == NULL) return true; // fast如果初始化为head.Next则中点在slow.Next // fast初始化为head,则中点在slow ListNode *slow = head, *fast = head->next; while(fast != NULL && fast->next != NULL){ slow = slow->next; fast = fast->next->next; } ListNode *tail = reverseList(slow->next); // 断开两个链表(需要用到中点前一个节点) slow->next = NULL; while(head != NULL && tail != NULL){ if(head->val != tail->val) return false; head = head->next; tail = tail->next; } return true; } ListNode *reverseList(ListNode *head){ if(head == NULL) return head; ListNode *pre = NULL; while(head != NULL){ ListNode *temp = head->next; head->next = pre; pre = head; head = temp; } return pre; }

Python sol.

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ node_len = 0 ptr = lhead = rhead = head left = [] right = [] while ptr != None: node_len += 1 ptr = ptr.next if node_len == 1: return True if node_len%2 == 0: for n in range(node_len): if n < node_len/2: left.append(lhead.val) else: right.append(lhead.val) lhead = lhead.next if node_len%2 == 1: for n in range(node_len): if n < round(node_len/2): left.append(rhead.val) elif n > round(node_len/2): right.append(rhead.val) rhead = rhead.next print('left', left) print('right', right) if len(left) != len(right): return False else: for l in range(len(left)): if left[l] == right[len(left)-l-1]: continue else: return False return True
  • 大神解法
    想法:用兩個linked list複製原來的linked list,其中一個進行反轉,再跟另一個比對,就可以知道是否為回文
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ slow, fast, head_copy = head, head, head while(fast and fast.next): slow = slow.next fast = fast.next.next prev = slow curr = slow.next prev.next = None while(curr): tmp = curr.next curr.next = prev prev = curr curr = tmp while(prev != None and head_copy != None): if(prev.val != head_copy.val): return False prev = prev.next head_copy = head_copy.next return True
  • 更精簡的版本
class Solution(object): def isPalindrome(self, head): 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 = slow.next rev = rev.next return not rev