Palindrome Linked List : 判斷一個linked list它是否對稱
Python
方法一 :
先把數值放到一個list裡，接著判斷r[i] 和r[n-i-1] 是否相等，不相等返回False ，否則返回True
class Solution(object):
def isPalindrome(self, head):
if not head.next:
return True
l = [head.val]
while head.next:
head = head.next
l.append(head.val) #數值放到list
n = len(l)
for i in range(n//2):
if l[i]!=l[n-i-1]: #r[i] 和r[n-i-1] 是否相等
return False
return True方法二 : 雙指針
利用雙指針從頭尾開始向內一個一個比較
class Solution(object):
def isPalindrome(self, head):
tmep = []
while head:
temp.append(head.val) #數值放到list
head = head.next
n = len(temp)
left, right = 0, n - 1
while left < right:
if vals[left] != vals[right]: #從頭尾開始向內一個一個比較
return False
left += 1 #左端向右
right -= 1 #右端向左
return True方法三 : 快慢指針
設立fast跟slow兩個指標,一個一次走兩步,一個一次走一步，直到fast走到底為止，此時可以發現slow會在linked list近中央的位置，將slow之後的linked list全數反轉(pre剛好會是反轉後的頭)，這時我們只要一個指標從head開始,一個指標從pre開始，就能比較值來決定該linked list是否對稱了
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
fast=head
slow=head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
pre=None
while slow:
temp=slow.next
slow.next=pre
pre=slow
slow=temp
l=head
r=pre
while r:
if l.val!=r.val:
return False
l=l.next
r=r.next
return True方法四 : 直接翻轉
def isPalindrome(self, head: ListNode) -> bool:
vals = []
current_node = head
while current_node is not None:
vals.append(current_node.val)
current_node = current_node.next
return vals == vals[::-1] #python翻轉方法C++
雙指針法
1.遍歷鍊錶，將鍊錶中的元素依次存放到一個數組中。
2.使用雙指針法，比較數組的首尾元素是否相同，直到指針相遇或者不相同為止。
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals;
while (head != nullptr) {
vals.push_back(head->val);
head = head->next;
}
int left = 0, right = vals.size() - 1;
while (left < right) {
if (vals[left] != vals[right]) {
return false;
}
left++;
right--;
}
return true;
}
};快慢指針法
1.使用快慢指針法找到鍊錶的中點，可以將鍊錶分為前半部分和後半部分。
2.反轉鍊錶的後半部分。
3.比較鍊錶的前半部分和後半部分是否相同。
4.恢復鍊錶的後半部分。
5.返回比較結果。
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
ListNode* mid = getMid(head);
ListNode* half = reverseList(mid->next);
bool isPalindrome = true;
ListNode* p1 = head;
ListNode* p2 = half;
while (isPalindrome && p2 != nullptr) {
if (p1->val != p2->val) {
isPalindrome = false;
}
p1 = p1->next;
p2 = p2->next;
}
reverseList(half);
return isPalindrome;
}
ListNode* getMid(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};