高效判断回文链表的3种解法
LeetCode234
给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。（回文序列是向前和向后读都相同的序列。）
Python解法
1.变成数组
# 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: res = [] current = head while current is not None: res.append(current.val) current = current.next return res == res[::-1]2.快慢指针
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def get_mid(self, head): slow = head fast = head while fast.next is not None and fast.next.next is not None: slow = slow.next fast = fast.next.next return slow def reverse_list(self,node): cur = node pre = None while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre def isPalindrome(self, head: Optional[ListNode]) -> bool: if not head or not head: return True mid_node = self.get_mid(head) second_half = mid_node.next reverse_second = self.reverse_list(second_half) p1 = head p2 = reverse_second flag = True while flag and p2: if p1.val != p2.val: flag = False p1 = p1.next p2 = p2.next return flagJava解法
1.变成数组
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { int len = 0; ListNode cur = head; while(cur != null){ len++; cur = cur.next; } int[] arr = new int[len]; cur = head; for(int i = 0; i < len; i++){ arr[i] = cur.val; cur = cur.next; } int s = 0, f = len - 1; while(s < f){ if(arr[s] != arr[f])return false; s++; f--; } return true; } }2.快慢指针
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { // 快慢指针找前半段中点 private ListNode getMid(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 反转链表 private ListNode reverseList(ListNode node) { ListNode cur = node; ListNode pre = null; while (cur != null) { ListNode nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } return pre; } public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } ListNode midNode = getMid(head); ListNode secondHalf = midNode.next; ListNode revSecond = reverseList(secondHalf); ListNode p1 = head; ListNode p2 = revSecond; boolean flag = true; while (flag && p2 != null) { if (p1.val != p2.val) { flag = false; } p1 = p1.next; p2 = p2.next; } return flag; } }C++解法
1.变成数组
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { vector<int> res; ListNode* cur =head; while(cur != nullptr){ res.push_back(cur->val); cur = cur->next; } vector<int> rev(res.rbegin(), res.rend()); return res == rev; } };2.快慢指针
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { private: // 找中点 ListNode* getMid(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; } // 反转链表 ListNode* reverseList(ListNode* node) { ListNode* cur = node; ListNode* pre = nullptr; while (cur != nullptr) { ListNode* nxt = cur->next; cur->next = pre; pre = cur; cur = nxt; } return pre; } public: bool isPalindrome(ListNode* head) { if (head == nullptr || head->next == nullptr) { return true; } ListNode* midNode = getMid(head); ListNode* secondHalf = midNode->next; ListNode* revSecond = reverseList(secondHalf); ListNode* p1 = head; ListNode* p2 = revSecond; bool flag = true; while (flag && p2 != nullptr) { if (p1->val != p2->val) { flag = false; } p1 = p1->next; p2 = p2->next; } return flag; } };